7 强连通元件

对於一个无向图来说，如果我们把一个极大连通的子图找出来（极大在这边的定义是，无论再增加任何一个点，都没办法让现在的子图连通），那麽这个极大连通的子图就被我们称为连通元件。

对於有向图来说，其连通的定义是单方向的，因此有分为弱连通 (weakly connected) 以及强连通 (strongly connected)。

弱连通：只要对於任意两个点 u 和 v，至少有 "u 能走得到 v" 或 "v 能走得到 u”，就称为弱连通。
强连通：对於任意两个点 u 和 v，必须同时满足 “u 能走得到 v” 以及 “v 能走得到 u”。

由於 「u 和 v 能够互相走得到」这样的定义可以想像成「u 和 v 等价」，我们可以将一张图的所有顶点划分成许多能够互相走得到的等价类 (equivalence classes)。换句话说，在一张有向图中，可以合理地定义极大强连通子图，我们称之为强连通元件 (strongly connected component, SCC)。

7.1 找出强连通元件的 Kosaraju 演算法

方法其实很酷，也很简单，步骤如下：

• 第一步：对原本的图做一次 DFS，并且将每个节点依照 DFS 结束拜访的时间由晚到早重新排列顺序。
• 第二步：把所有的边反过来，依照重新排列的顺序做一次 DFS。这步每一次的 DFS 找出来的树，上面的点都属於同一个强连通元件。

比方说，考虑下面这张图以及做完第二步以後得到的强连通元件们(用同一种颜色表示)

7.2 一些应用

有一些图论的问题都可以藉由先找出强连通元件以後，把这些强连通元件全部缩起来。这麽一来，这个图就会变成有向无环图 (directed acyclic graph, DAG)。在这样的图上就可以定义拓朴排序，很多问题就可以迎刃而解啦。也可以试试看隐写术，把一张黑白的图用强连通元件的方式藏起来，只要计算强连通元件就可以复原整张图的概念。

7.X 冷笑话

为什麽上面那两张图都长得很像？因为它们都是有像图啊。