xxx 强连通分量（Tarjan算法）

题目描述
给定一个有向图，找出其所有的强连通分量。强连通分量是有向图的一个极大子图，其中任意两个顶点都互相可达。

解题过程
Tarjan算法通过一次深度优先搜索（DFS）即可找出所有强连通分量，核心在于维护每个顶点的搜索顺序（索引）和能回溯到的最早祖先索引。

1. 初始化

   • 为每个顶点分配唯一索引（index），记录访问顺序。
   • 维护一个栈（stack）存储当前DFS路径中的顶点。
   • 定义两个数组：
     • index[i]：顶点i的访问索引。
     • lowLink[i]：顶点i能回溯到的最小祖先索引。
   • 初始化所有顶点的索引为未定义（-1），并设置当前索引计数器为0。

2. DFS遍历与索引分配
   对每个未访问的顶点进行DFS：

   • 设置其index和lowLink为当前索引值，索引计数器加1。
   • 将该顶点压入栈，并标记为在栈中。

3. 处理邻居顶点
   遍历当前顶点的所有出边邻居：

   • 若邻居未访问，递归DFS，更新当前顶点的lowLink为：

     lowLink[u] = min(lowLink[u], lowLink[v])
     

   • 若邻居已在栈中（说明是当前DFS路径中的祖先），更新：

     lowLink[u] = min(lowLink[u], index[v])
     

4. 判断强连通分量的根
   回溯时，若某顶点的lowLink等于其index，说明它是当前强连通分量的根。此时：

   • 不断从栈中弹出顶点，直到弹出该根顶点。
   • 弹出的所有顶点构成一个强连通分量。

5. 示例
   考虑有向图：边集为 (0→1), (1→2), (2→0), (1→3), (3→4)。

   • 从顶点0开始DFS，索引分配：0:0, 1:1, 2:2。
   • 顶点2的邻居0已访问且在栈中，更新lowLink[2] = min(2,0) = 0。
   • 回溯时，顶点1的lowLink被更新为0，顶点0的lowLink=0等于其索引0，弹出栈中{0,1,2}作为一个分量。
   • 继续处理顶点3和4，得到分量{3}和{4}。

关键点

• 算法时间复杂度为O(V+E)，适用于大规模稀疏图。
• lowLink的更新策略确保能准确识别分量边界。
• 栈的使用避免重复访问已确定的强连通分量。