强连通分量（Tarjan算法）

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

解题过程：

1. 基本概念

   • 强连通分量（SCC）是图论中的重要概念，用于分析有向图的连通性结构
   • Tarjan算法通过一次DFS遍历就能找出所有SCC，时间复杂度为O(V+E)

2. 核心数据结构

   • 为每个节点维护三个值：
     • index：DFS遍历的访问顺序编号
     • lowlink：从该节点出发能到达的最小索引值
     • onStack：标记节点是否在栈中

3. 算法步骤

   • 初始化全局索引计数器为0，创建一个空栈
   • 对每个未访问的节点执行DFS：
     a. 设置节点的index和lowlink为当前索引值，然后索引值加1
     b. 将节点压入栈中，标记onStack为true
     c. 遍历节点的所有邻居：
     • 如果邻居未被访问，递归访问它，然后更新当前节点的lowlink
     • 如果邻居在栈中，用邻居的index更新当前节点的lowlink
       d. 如果当前节点的lowlink等于index，说明找到了一个SCC：
     • 不断弹出栈顶元素，直到弹出当前节点
     • 弹出的所有节点组成一个强连通分量

4. 关键原理

   • lowlink相等的节点属于同一个SCC
   • 栈用于保证SCC的完整性
   • 当lowlink == index时，说明找到了一个SCC的根节点

5. 实例演示
   考虑有向图：0→1→2→0（环）和3→4

   • 从节点0开始DFS，最终会识别出{0,1,2}是一个SCC
   • 节点3和4各自形成单独的SCC

这个算法高效地利用了DFS的性质和栈结构，能够在线性时间内完成SCC的检测。