有向无环图移除入度为0顶点后的子图数量计算求助

核心转化 #

首先明确：通过移除无入边顶点操作能得到的图，对应的顶点子集是原DAG的上闭集（传递闭包意义下）——即若顶点v在子集中，则v所有能到达的顶点也必须在子集中。因此问题等价于计算该DAG的上闭集总数。

分层建模 #

由于路径最大长度为5，可将DAG按拓扑序分为6层（层0为无入边顶点，层i的顶点最长路径长度为i，层5为最长路径的终点）。每个顶点仅属于一层，层间仅存在从低到高（层i到层i+1及以上）的边。

动态规划与分组优化 #

按层从后往前（层5到层0）递推计算上闭集数量，利用顶点后代集合的相似性减少计算量：

• 层5处理：层5顶点无后代，任意子集都是上闭集，数量为2^n5（n5为层5顶点数）。
• 层i（i<5）处理：
  1. 预处理每个层i顶点的后代集合（即层i+1到5中该顶点能到达的所有顶点，必然是上闭集）。
  2. 将后代集合相同的顶点归为一组，统计每组的顶点数。
  3. 结合层i+1到5的上闭集计数结果，计算当前层与上层合并后的上闭集总数：
     • 对于每个后代集合分组，若选择加入组内顶点，需保证上层上闭集包含该后代集合；若不加入，无约束。
     • 利用乘法原理和容斥思想，将分组的选择数相乘，快速得到总数量（无需枚举所有上闭集）。

关键细节 #

• 对于层i的顶点分组，每组的贡献为(1 + g)^c，其中g是上层中包含该组后代集合的上闭集数量，c是组内顶点数。
• 上层中包含某后代集合的上闭集数量，可通过计算该集合外顶点构成的子DAG的上闭集数量得到（因原集合是上闭集，外部顶点的后代不会落入集合内）。

内容的提问来源于stack exchange，提问作者Ordev Agens