有向无环图（DAG）的传递闭包问题

题目描述

给定一个 有向无环图（DAG），其包含 n 个顶点（编号为 0 到 n-1）和 m 条有向边。你需要计算出这个图的 传递闭包（Transitive Closure）。

什么是传递闭包？
在一个有向图中，如果存在一条从顶点 u 到顶点 v 的 路径（路径长度可以为 0，即 u=v），那么我们称顶点 v 是 从 u 可达的。图的传递闭包是一个 n × n 的布尔矩阵 T，其中 T[u][v] = true 当且仅当在图中存在一条从 u 到 v 的路径（即 v 从 u 可达）。

输入：n 个顶点，m 条边，每条边由 (u, v) 表示，表示一条从 u 指向 v 的有向边。
输出：一个 n×n 的布尔矩阵，表示传递闭包。

注意：因为图是 DAG，所以不存在环，这可以简化某些算法的实现和思考。

解题思路详解

计算传递闭包的核心是：对于每个顶点 u，找出所有从 u 出发能够到达的顶点 v。在 DAG 中，我们可以利用其 无环 的特性，通过 拓扑排序 来有序地传播可达性信息。

总体思路如下：

1. 对 DAG 进行 拓扑排序，得到一个顶点序列，保证对于任意有向边 (u, v)，u 在序列中都出现在 v 之前。
2. 按照拓扑排序的 逆序（从后往前）或者 顺序（从前往后）进行动态规划，来递推计算可达性。
   • 这里我们采用 从后往前（即拓扑逆序） 的方式：因为如果 u 在 v 之前，那么当我们处理 u 时，所有从 u 的后继（包括间接后继）的可达信息都已经计算好了，我们可以直接合并这些信息。

具体步骤我们一步步来讲解。

步骤 1：拓扑排序

因为图是 DAG，我们可以使用 Kahn 算法或基于 DFS 的算法得到拓扑排序。

以 Kahn 算法为例：

• 计算每个顶点的 入度（In-degree），即有多少条边指向它。
• 将入度为 0 的顶点加入队列。
• 当队列非空时，取出队首顶点 u，将其加入拓扑序列，然后对于 u 的每个邻接点 v，将 v 的入度减 1；如果减后 v 的入度为 0，则将 v 入队。
• 最终得到的序列就是一个拓扑排序。

例子：
假设 DAG 有 4 个顶点，边为：0→1, 0→2, 1→3, 2→3。
拓扑排序可能是 [0, 1, 2, 3] 或 [0, 2, 1, 3] 等，只要保证每个边的起点在终点之前即可。

步骤 2：初始化可达矩阵

我们创建一个 n×n 的布尔矩阵 reach，初始时：

• reach[i][i] = true（每个顶点可以到达自己）。
• 对于每条边 (u, v)，reach[u][v] = true（直接可达）。

注意：在编程中，我们可以用二维数组 bool reach[n][n] 或 bitset<n> 来表示，后者在空间和时间上通常更高效（特别是 n 较大时）。

步骤 3：按拓扑逆序递推

我们得到拓扑序列 topo 后，从后往前 遍历每个顶点 u：

• 对于 u 的每个直接后继 v（即存在边 u→v），我们需要将 v 可达的所有顶点，也标记为从 u 可达。
• 因为我们是逆序处理，所以当我们处理 u 时，v 的可达信息 reach[v][*] 已经计算完毕（v 在拓扑序列中位于 u 之后，所以我们先处理 v，后处理 u）。

递推关系：
对于每个 u 和它的每个直接后继 v：

对于所有顶点 w：
    如果 reach[v][w] 为 true，则设置 reach[u][w] = true。

实际上，这相当于进行布尔矩阵的“或”操作：reach[u] |= reach[v]（如果我们将 reach[u] 看作一个 bitset）。

为什么逆序有效？
因为 DAG 中，如果 u 能到达 v，那么 v 在拓扑序中一定在 u 之后。当我们逆序处理时，先处理 v（及其更后面的顶点），后处理 u，这样 u 在合并 v 的可达信息时，v 的可达信息已经是完整的（包含了 v 的所有后继的可达性）。

步骤 4：输出结果

遍历 reach 矩阵，输出每个 reach[i][j] 的值（true 或 1，false 或 0）。

完整算法流程（伪代码）

输入：n, m, 边列表 edges[]
输出：n×n 的传递闭包矩阵

1. 根据 edges 构建邻接表 adj 和入度数组 indegree。
2. 进行拓扑排序，得到序列 topo：
   队列 q
   将所有 indegree[i]==0 的顶点 i 入队
   while q 非空:
       u = q.pop()
       将 u 加入 topo
       for v in adj[u]:
           indegree[v]--
           if indegree[v]==0:
               将 v 入队

3. 初始化 n×n 布尔矩阵 reach 为 false
   for i = 0 to n-1:
       reach[i][i] = true
   for each edge (u, v) in edges:
       reach[u][v] = true

4. 按照 topo 的逆序处理每个顶点 u：
   for i = n-1 down to 0:
       u = topo[i]
       for each v in adj[u]:   // v 是 u 的直接后继
           for w = 0 to n-1:
               if reach[v][w] == true:
                   reach[u][w] = true
           // 优化：实际可以用 bitset 的按位或操作：reach[u] |= reach[v]

5. 输出 reach 矩阵。

时间复杂度和优化

• 基本方法（三重循环）：O(n³ + n + m)，因为最内层对 w 的循环是 O(n)。
• 使用 bitset 优化：将 reach[u] 用一个 bitset 表示，那么 reach[u] |= reach[v] 可以在 O(n/word_size) 时间内完成（通常 word_size=32 或 64）。这样总复杂度降为 O(n³/word_size + n + m)，对于 n 达到几千的情况也能较快运行。
• 拓扑排序本身是 O(n + m)。

举例说明

考虑一个简单的 DAG：

• n=4
• 边：0→1, 0→2, 1→3, 2→3

步骤 1：拓扑排序得到序列 [0, 1, 2, 3]。

步骤 2：初始化 reach 矩阵（1 表示 true，0 表示 false）：

步骤 3：逆序遍历拓扑序列 [3, 2, 1, 0]：

• 处理顶点 3：没有后继，不变。
• 处理顶点 2：后继是 3，将 reach[2] 与 reach[3] 合并（已经合并了，因为 reach[2][3] 已是 1）。
• 处理顶点 1：后继是 3，合并后 reach[1][3] 已是 1。
• 处理顶点 0：后继是 1 和 2。
  • 合并 reach[1]：reach[0] 变为 [1,1,1,1]（因为 reach[1][3]=1）。
  • 合并 reach[2]：reach[0] 已经是 [1,1,1,1]，不变。

最终 reach 矩阵：

这就是传递闭包：例如，从 0 可以到达 3（路径 0→1→3 或 0→2→3）。

总结

对于 DAG 的传递闭包问题，我们利用拓扑排序确定顶点的处理顺序，然后通过动态规划（从后往前）合并后继的可达信息，从而高效地计算出任意两个顶点之间的可达性。使用 bitset 可以大幅优化实际运行时间。