Tarjan算法求有向图的强连通分量

题目描述
给定一个有向图，要求找出图中所有的强连通分量（Strongly Connected Components, SCC）。强连通分量是指有向图中的一个最大子图，其中任意两个顶点都互相可达。例如，在下图中有三个强连通分量：{A, B, E}、{C, D} 和 {F}。

A -> B -> F  
|    ^     |
v    |     v  
E -> D <- C  

注意：本题与 Kosaraju 算法不同，Tarjan 算法仅需一次深度优先搜索（DFS）即可求解。

解题过程
Tarjan 算法的核心思想是利用 DFS 遍历图，并通过维护每个节点的“发现时间”和“能回溯到的最早祖先”来识别强连通分量。以下是详细步骤：

1. 基本概念与数据结构

• 索引（index）：每个节点第一次被访问时的顺序编号（从 0 或 1 开始）。
• 低链接值（lowlink）：节点通过有向边能回溯到的最小索引值（包括自身、后代或横向边）。
• 栈（stack）：临时存储当前 DFS 路径中未归属到某个 SCC 的节点。
• 数组 visited[]：标记节点是否在栈中，避免重复处理。

初始化：所有节点的索引为 -1（未访问），低链接值初始为索引值，栈为空。

2. DFS 遍历与索引分配
从任意未访问节点开始 DFS。对当前节点 u：

• 设置其索引和低链接值为当前索引计数器（如 index = 0, lowlink = 0），计数器递增。
• 将 u 压入栈，并标记为“在栈中”。
• 遍历 u 的每个邻居 v：
  • 若 v 未访问（索引为 -1），递归访问 v，并在回溯时更新：
    u.lowlink = min(u.lowlink, v.lowlink)。
  • 若 v 已访问且在栈中（说明是当前 DFS 树中的祖先或横向边），更新：
    u.lowlink = min(u.lowlink, v.index)。

3. 强连通分量判定
DFS 回溯到 u 时，若 u.lowlink == u.index，说明 u 是一个 SCC 的根节点（无法回溯到更早的节点）。此时：

• 从栈中弹出节点，直到弹出 u 为止，这些节点构成一个 SCC。
• 将弹出的节点标记为“不在栈中”。

4. 完整示例
以图 A→B, B→C, C→A, B→D, D→E, E→F, F→D 为例：

• 从 A 开始 DFS：索引 A=0, B=1, C=2。C 指向已访问的 A（在栈中），更新 C.lowlink=min(2,0)=0。
• 回溯到 B：B.lowlink=min(1, C.lowlink=0)=0。回溯到 A：A.lowlink=min(0, B.lowlink=0)=0。此时 A 满足根条件，弹出 {A, B, C} 作为 SCC1。
• 继续访问 D=3, E=4, F=5。F 指向 D（索引 3，在栈中），更新 F.lowlink=3。回溯更新 E.lowlink=3, D.lowlink=3。D 为根，弹出 {D, E, F} 作为 SCC2。

5. 关键点

• 低链接值更新需注意横向边（cross-edge）和回边（back-edge）的处理。
• 栈仅存储当前路径相关节点，确保 SCC 不重叠。
• 时间复杂度为 O(V+E)，与 DFS 相同。

通过以上步骤，Tarjan 算法能高效且一次性地找出所有强连通分量。