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

题目描述
给定一个有向图，找出其所有的强连通分量（SCC）。强连通分量是指图中的一个最大子图，其中任意两个顶点都互相可达。Kosaraju算法是一种高效且直观的求解SCC的算法，其核心思想是通过两次深度优先搜索（DFS）来实现。

解题过程

1. 算法概述
   Kosaraju算法的步骤分为三个阶段：

   • 第一次DFS：对原图进行DFS，记录顶点的完成时间（即DFS遍历结束的顺序）。
   • 计算转置图：将原图的所有边反向，得到转置图。
   • 第二次DFS：按照第一次DFS的完成时间倒序（即从最后完成的顶点开始），对转置图进行DFS。每次DFS遍历得到的顶点集合就是一个强连通分量。

2. 步骤详解
   步骤1：第一次DFS（记录完成顺序）

   • 初始化一个空栈（用于记录完成顺序）和一个访问标记数组。
   • 对原图的每个未访问顶点执行DFS：
     • 访问顶点时标记为已访问。
     • 递归访问其所有未访问的邻接顶点。
     • 当顶点的所有邻接顶点都被处理完毕后，将该顶点压入栈中（此时记录的是完成时间，后完成的顶点先入栈）。
   • 示例：对图 A→B, B→C, C→A（三个顶点形成环），DFS可能从A开始，依次访问A、B、C，完成顺序为C、B、A（栈顶为A）。

   步骤2：构建转置图

   • 创建一个新图，将原图中的每条边u→v反向为v→u。
   • 示例：原图的边A→B, B→C, C→A的转置图为B→A, C→B, A→C。

   步骤3：第二次DFS（按倒序处理转置图）

   • 初始化一个新的访问标记数组。
   • 从栈中依次弹出顶点（即按第一次DFS的完成时间倒序），对每个未访问的顶点在转置图上执行DFS：
     • 本次DFS遍历到的所有顶点属于同一个强连通分量。
   • 示例：在转置图中，按顺序A、B、C（栈弹出顺序）处理。若从A开始DFS，会访问A、C、B（因为转置图边为A→C, C→B, B→A），这三个顶点互相可达，构成一个SCC。

3. 算法正确性解释

   • 第一次DFS的目的是确定顶点的“拓扑顺序”（尽管有环，但完成时间仍能反映依赖关系）。
   • 转置图的作用是：将原图中SCC内部的连通性保留，但SCC之间的边被反向。在转置图中，从“最晚完成”的顶点开始DFS，能确保先遍历到的是“源头”SCC，避免跨分量访问。

4. 复杂度分析

   • 时间复杂度：两次DFS和构建转置图均为O(V+E)，其中V为顶点数，E为边数。
   • 空间复杂度：O(V+E)存储图和栈。

总结
Kosaraju算法通过两次DFS巧妙地利用图的结构特性，高效分解强连通分量。关键点在于理解完成时间顺序和转置图的作用，确保分量被正确隔离。