强连通分量(strongly connected component)

组别：提高级
难度：7

一个有向图的强连通分量是指在该子图中的任意两个顶点之间都存在路径的子图。

具体来说，如果一个有向图的每一对顶点 u 和v，都存在从 u 到 v 和从 v 到 u 的路径，那么这些顶点组成的子图就是一个强连通分量。

强连通分量的性质

1. 自反性：每个顶点本身就是一个强连通分量。
2. 对称性：如果顶点 u 和 v 在同一个强连通分量中，那么 v 和 u 也在同一个强连通分量中。
3. 传递性：如果顶点 u 和 v 在同一个强连通分量中，并且 v 和 w 也在同一个强连通分量中，那么 u 和 w 也在同一个强连通分量中。

计算强连通分量的方法

计算强连通分量常用的方法主要有两种：Kosaraju算法和Tarjan算法。

Kosaraju算法

Kosaraju算法的步骤如下：

1. 对图进行深度优先搜索（DFS），记录每个顶点的完成时间。
2. 反转图中的所有边。
3. 根据第一步中记录的完成时间，对反转后的图进行深度优先搜索，每次搜索得到的子图就是一个强连通分量。

Tarjan算法

Tarjan算法利用了DFS，并且在一次遍历中就可以找到所有的强连通分量。具体步骤如下：

1. 使用DFS遍历图，维护每个节点的发现时间和通过该节点能够到达的最早时间。
2. 使用一个栈记录DFS路径。
3. 当发现一个强连通分量时，将栈中对应的节点全部弹出。