有向图的强连通分量（Kosaraju算法）

题目描述
给定一个有向图，要求找出图中所有的强连通分量。强连通分量是指图中的一个最大子图，其中任意两个顶点都互相可达。你需要实现Kosaraju算法来解决这个问题。

解题过程

1. 理解强连通分量

   • 在有向图中，如果从顶点u到v存在一条路径，并且从v到u也存在一条路径，那么u和v是强连通的
   • 强连通分量是最大的强连通子图（不能再添加其他顶点而保持强连通性）
   • 整个图可以被分解为若干个强连通分量

2. Kosaraju算法核心思想

   • 算法基于一个关键观察：如果将图的所有边反向，强连通分量的组成不会改变
   • 通过两次深度优先遍历来找出强连通分量

3. 具体步骤

   第一步：第一次DFS遍历（在原图上）

   • 对原图进行深度优先搜索
   • 在递归返回时（即完成对某个顶点的探索时），将顶点压入栈中
   • 这样可以保证栈顶的顶点在强连通分量图中是"较后"的

   第二步：构建转置图

   • 创建原图的一个转置图（将所有边的方向反转）
   • 如果原图中有一条边u→v，那么在转置图中就有一条边v→u

   第三步：第二次DFS遍历（在转置图上）

   • 按照栈的弹出顺序（从栈顶开始）对转置图进行DFS
   • 每次DFS遍历能够到达的顶点构成一个强连通分量

4. 算法执行示例
   假设有向图：1→2→3→1 和 3→4→5

   第一次DFS（原图）：

   • 从顶点1开始：1→2→3→4→5
   • 完成顺序：5,4,3,2,1（栈顶为1）

   转置图：2→1, 3→2, 1→3, 4→3, 5→4

   第二次DFS（转置图）：

   • 从栈顶顶点1开始：只能访问1,2,3 → 第一个强连通分量{1,2,3}
   • 接着从栈中取4：只能访问4 → 第二个强连通分量{4}
   • 最后从栈中取5：只能访问5 → 第三个强连通分量{5}

5. 算法复杂度分析

   • 时间复杂度：O(V+E)，其中V是顶点数，E是边数
   • 空间复杂度：O(V+E)，用于存储图和转置图

6. 应用场景

   • 编译器中的代码优化
   • 社交网络中的社区发现
   • 电路设计中的连接性分析