Tarjan算法求有向图的强连通分量 题目描述 给定一个有向图 \( G = (V, E) \)，要求找出图的所有强连通分量（Strongly Connected Components, SCC）。强连通分量是图的一个极大子图，其中任意两个顶点 \( u \) 和 \( v \) 均相互可达（即存在从 \( u \) 到 \( v \) 和从 \( v \) 到 \( u \) 的路径）。例如，社交网络中的紧密社群或代码中的循环依赖检测均需此算法。 解题过程 Tarjan算法通过一次深度优先搜索（DFS）即可找出所有SCC，核心在于维护每个顶点的 访问序号 （ index ）和 低链接值 （ lowlink ），并用栈记录当前路径上的顶点。 步骤详解 初始化全局变量 index ：记录DFS遍历的访问顺序，从0开始。 stack ：保存当前DFS路径上的顶点。 on_stack ：标记顶点是否在栈中。 lowlink ：记录每个顶点能回溯到的最小 index 。 DFS遍历每个未访问顶点 对每个顶点 \( v \)： 设置 index[v] 和 lowlink[v] 为当前 index 值，并递增 index 。 将 \( v \) 入栈，标记 on_stack[v] = true 。 遍历邻居顶点 对于 \( v \) 的每个邻居 \( w \)： 若 \( w \) 未访问（无 index ），递归访问 \( w \)，然后更新： \[ lowlink[ v] = \min(lowlink[ v], lowlink[ w ]) \] 若 \( w \) 已在栈中（说明 \( w \) 与 \( v \) 在同一个DFS分支），更新： \[ lowlink[ v] = \min(lowlink[ v], index[ w ]) \] 判断SCC的根节点 当 \( v \) 的所有邻居处理完毕后，若 lowlink[v] == index[v] ，说明 \( v \) 是一个SCC的根节点。此时不断出栈，直到 \( v \) 出栈为止，出栈的所有顶点构成一个SCC。 示例演示 考虑有向图：边为 \( A \to B, B \to C, C \to A, C \to D, D \to E, E \to F, F \to D \)。 从A开始DFS：A、B、C依次入栈， lowlink 在A、B、C间传递后均变为0（因C可回溯到A）。 回溯至A时， lowlink[A] = index[A] = 0 ，出栈{A,B,C}为一个SCC。 继续访问D、E、F：D、E、F入栈，F指向D时更新 lowlink[F] = index[D] = 3 。 回溯至D时， lowlink[D] = index[D] ，出栈{D,E,F}为另一个SCC。 结果：SCC为 {A,B,C} 和 {D,E,F}。 关键点 低链接值更新 ：通过邻居的 lowlink 或 index 回溯，识别环路。 栈的作用 ：确保同一SCC的顶点在回溯时被正确分组。 时间复杂度 ：\( O(|V| + |E|) \)，因每个顶点和边仅处理一次。