已知拓扑排序，求符合条件的有向无环图数量的方法

已知线性拓扑序列为(1,2,3,4)，求含4条边、无重边的有向无环图（DAG）中，存在能到达所有顶点的顶点（仅可能是拓扑首元素1）的图的数量，最终结果模m（m≤200000）。该问题可推广为：给定n个顶点的线性拓扑序列，求含k条边且1能到达所有顶点的DAG数量模m。

核心结论 #

对于线性拓扑序列1→2→…→n，合法DAG的边只能是i→j（i<j）。要让1能到达所有顶点，等价于每个后续顶点至少有一条来自前面可达顶点的边。我们可以通过动态规划结合组合数预处理来高效计算结果。

具体解法 #

1. 动态规划定义 #

设dp[i][t]表示前i个顶点构成的DAG中，1能到达所有i个顶点，且恰好有t条边的图的数量。

2. 初始状态 #

• dp[1][0] = 1：仅含顶点1，0条边，满足1到达所有顶点的条件。
• 其余dp[1][t] = 0（t≠0）：顶点1无法构成t≠0条边的图。

3. 递推公式 #

对于i≥2，加入第i个顶点时，必须至少选择1条从{1,2,…,i-1}到i的边（共i-1条可选边）。设选择s条这类边（1≤s≤min(i-1, t)），则前i-1个顶点需要有t-s条边且满足1能到达所有前i-1个顶点：

dp[i][t] = Σ（s从1到min(i-1, t)） dp[i-1][t-s] * C(i-1, s)

其中C(a,b)是组合数，表示从a条边中选b条的方案数，结果模m。

4. 组合数预处理 #

预处理组合数C(a,b)（0≤b≤a≤n-1），递推公式为：

• C(a,0) = 1，C(a,a) = 1
• C(a,b) = (C(a-1,b-1) + C(a-1,b)) % m（0<b<a）

5. 空间优化 #

使用两个一维数组prev_dp和curr_dp分别存储dp[i-1]和dp[i]的值，每次计算完成后替换数组，节省空间。

示例验证（n=4，k=4） #

1. 预处理组合数：C(1,1)=1，C(2,1)=2，C(2,2)=1，C(3,1)=3，C(3,2)=3
2. 计算dp数组：
   • dp[1] = [1, 0, 0, 0, 0]
   • dp[2][1] = dp[1][0] * C(1,1) = 1，其余为0 → dp[2] = [0,1,0,0,0]
   • dp[3][2] = dp[2][1] * C(2,1) = 2；dp[3][3] = dp[2][1] * C(2,2) =1 → dp[3] = [0,0,2,1,0]
   • dp[4][4] = dp[3][2]*C(3,2) + dp[3][3]*C(3,1) = 2*3 +1*3=9

最终结果为9，与枚举验证一致。

复杂度分析 #

• 组合数预处理：O(n²)，n≤600时完全可行。
• 动态规划：O(nk)，对于n≤600、k≤2e5的场景，计算量在可接受范围内。

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