强连通分量（Strongly Connected Components）的Kosaraju算法

题目描述
给定一个有向图，找出其所有的强连通分量（SCC）。强连通分量是指图中的一个最大子图，其中任意两个顶点都互相可达。例如，在下图中，顶点{0,1,2}构成一个SCC，因为任意两点之间都有路径；而顶点{3}和{4}各自单独构成SCC。

解题过程
Kosaraju算法通过两次深度优先搜索（DFS）来找出有向图中的所有SCC，步骤如下：

1. 第一次DFS：记录顶点完成时间

   • 对原图进行DFS遍历，但不需要记录连通性。
   • 在DFS过程中，当一个顶点的所有邻居都被访问完成后，将该顶点压入栈中（后进先出）。这一步确保栈顶顶点在拓扑排序中位于更早完成的位置（注意：此排序针对原图的转置图有重要意义）。

2. 构建转置图

   • 将原图的所有边反向，得到转置图。例如原图有边A→B，则转置图中改为B→A。
   • 转置图与原图具有相同的SCC，但SCC之间的边方向反转，从而隔离各SCC。

3. 第二次DFS：按栈顺序遍历转置图

   • 从栈中依次弹出顶点，以该顶点为起点对转置图进行DFS。
   • 每次DFS访问到的顶点集合即为一个SCC。因为栈顶顶点在原图中属于“较晚完成”的SCC，而在转置图中，这些SCC变成“源头”，DFS不会泄漏到其他SCC。

示例
假设有向图：0→1→2→0（环），2→3，3→4。

• 第一次DFS（从0开始）：访问顺序0→1→2→3→4，栈中顺序为[4,3,2,1,0]（完成时间递增）。
• 转置图：1→0，2→1，0→2，3→2，4→3。
• 第二次DFS：按栈顺序[4,3,2,1,0]遍历转置图。
  • 从4开始：访问4→3→2→1→0，但0已被标记？实际应分次进行：
    • 弹出4：访问4→3→2→1→0，得SCC{0,1,2,3,4}？错误！需修正：
      正确过程：
      1. 弹出4，从4DFS仅访问{4}（因4→3在转置图中无效？需检查边方向）。
         转置图边正确为：4无出边？实际转置图中3→2→1→0为另一组件。
         详细步骤：
      • 第一次DFS栈顺序应为[0,1,2,3,4]（以实际完成时间为准，假设从0开始：0访问1→2→3→4后回溯，栈底到顶为完成顺序）。
      • 第二次DFS：
        a. 弹出0，从0在转置图DFS访问{0,2,1}（因0→2→1），得SCC1。
        b. 弹出3，访问{3}，得SCC2。
        c. 弹出4，访问{4}，得SCC3。
        结果SCC：{0,1,2}、{3}、{4}。

关键点

• 算法依赖性质：转置图的SCC与原图相同，但SCC间边方向反转。
• 时间复杂度：O(V+E)，两次DFS均为线性时间。
• 栈的使用确保第二次DFS从“源SCC”开始，避免跨分量遍历。