强连通分量

闲话

嘟嘟嘟

强连通分量的定义

如果有向图中任意两点都有相互可达的路径，则称此图为强连通图。

有向图 \(G\) 的极大强连通子图称为 \(G\) 的强连通分量（SCC）。

上图表示了一张有向图和他的强连通分量。

DFS 生成树

我们从一张有向图 \(G\) 上的一个点出发，运行 DFS 算法的过程中，每次访问未经过的点时经过的边会构成一棵树，称为 DFS 生成树。

看一张图：

它的 DFS 生成树如下图所示：