寻找有向图中的强连通分量（Tarjan算法） 题目描述 在有向图 G=(V, E) 中，如果从顶点 u 出发可以到达顶点 v，并且从 v 出发也可以到达 u，则称 u 和 v 是强连通的。有向图的强连通分量是其极大强连通子图，即不能再添加任何顶点仍然保持强连通性质。题目要求找出给定有向图的所有强连通分量。 解题过程 Tarjan算法通过一次深度优先遍历（DFS）即可找出所有强连通分量，其核心思想是利用DFS生成树，并通过维护每个顶点的“遍历序号”和“可回溯到的最早祖先序号”来判断强连通分量。 步骤详解 定义关键数据结构 为每个顶点 v 维护两个值： index[v] ：顶点 v 在DFS中被访问的顺序编号（时间戳）。 lowlink[v] ：从 v 出发，通过有向边和DFS树边，能回溯到的 最早 祖先的 index 值（即能到达的最小的 index ）。 使用一个栈 S 来存储当前DFS路径上的顶点。 布尔数组 onStack[v] 记录顶点 v 是否在栈中。 DFS遍历与值更新 从任意未访问的顶点开始DFS。对当前顶点 v： 设置 index[v] 和 lowlink[v] 为当前时间戳，时间戳递增。 将 v 压入栈 S ，并标记 onStack[v] = true 。 遍历 v 的每个邻接顶点 w： 如果 w 未被访问（ index[w] 未定义），则递归访问 w，然后更新： lowlink[v] = min(lowlink[v], lowlink[w]) 。 （因为 v 能通过树边到达 w，而 w 能回溯到的祖先，v 也可能通过 w 回溯到。） 如果 w 已被访问且在栈中（ onStack[w] == true ），说明 w 在当前DFS路径上，则更新： lowlink[v] = min(lowlink[v], index[w]) 。 （注意此处是 index[w] 而不是 lowlink[w] ，因为从 v 到 w 是有向边，但 w 可能已属于其他强连通分量？实际上，若 w 在栈中，说明 w 与 v 在同一DFS递归链中，可能属于同一强连通分量，用 index[w] 确保能回溯到该路径上的最早点。） 识别强连通分量 当 v 的所有邻接点处理完后，检查 lowlink[v] ： 如果 lowlink[v] == index[v] ，说明 v 是某个强连通分量的“根”（该分量中最早被访问的顶点）。此时： 不断从栈 S 中弹出顶点，直到弹出 v 为止。 弹出的这些顶点构成一个强连通分量。 将弹出的顶点的 onStack 标记为 false 。 算法流程 对图中每个未访问顶点执行上述DFS过程。由于每个顶点只入栈、出栈一次，每条边只访问一次，时间复杂度为 O(|V| + |E|)。 为什么这样能找出强连通分量？ lowlink[v] 表示从 v 出发能触达的、在栈中的最早访问顶点。 如果 lowlink[v] == index[v] ，说明 v 无法回溯到更早的顶点，即 v 的子树中所有能回溯到的顶点都不会早于 v，因此 v 是某个强连通分量的根。 栈 S 保证了在遇到根 v 时，栈中 v 之上的顶点都是 v 的子孙，并且它们与 v 相互可达（通过 lowlink 的传递性），从而构成一个强连通分量。 示例 考虑有向图：顶点 0→1, 1→2, 2→0, 1→3, 3→4。 执行Tarjan算法： 从0开始DFS，递归访问0→1→2→0（回边），回溯时更新 lowlink。 顶点0的 lowlink 最终为0（等于 index），弹出栈中 {0,1,2} 作为一个强连通分量。 然后访问3和4，各自形成单独的强连通分量 {3} 和 {4}。 最终强连通分量为：{0,1,2}, {3}, {4}。