Tarjan 算法求解强连通分量

在 《Tarjan 算法的思路》中我们已经给出了 Tarjan 算法中的比较重要的几个元素，我们在这里重新复习一下：

1. DFN[] 数组：数组存储访问顺序，也就是遍历的点会分配一个序号（从小到大），然后序号存在这个数组当中：DFN[u]为节点 u 搜索的次序编号；
2. LOW[] 数组：表示该点能直接或间接到达时间最小的顶点。例如：LOW[u]为节点 u 的子树能够追溯到最早的栈中节点的次序号；
3. stack 存储该连通子图中的所有点。

下面我们来聊一聊这几个东西要怎么用。

什么是强连通分量

我们先给出一个强连通分量的定义：在有向图 G 中，如果两个顶点 u, v 之间存在一条 u 到 v 的路径，也存在一个 v 到 u 的路径，则称这两个顶点 u, v 是强连通的（strongly connected）。如果有向图 G 的任意两个顶点都强连通，则称 G 是一个强连通图。

非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量，总共三个强连通分量。

算法过程

我们先给出一个演示 Tarjan 算法的经典图，从根结点 1 开始DFS，把遍历到的节点入栈（1-3-5-6），当搜索到 u=6 的时候，DFN[6] = LOW[6]，当 DFN == LOW 的时候，我们认为找到一个强连通分量。然后执行弹栈操作，直到 u == v 为止，{6} 为一个强连通分量。

此时我们在图中标记一下 6 节点，计作 DFN = 4，LOW = 4。之后回溯到 5 节点，发现 DFN[5] == LOW[5] ，同 6 节点一样继续进行弹栈操作， {5} 为一个强连通分量。

回溯到结点 3，继续 DFS 搜索到结点 4，把 4 进栈。这时发现节点 4 向节点 1 有后向边，节点 1 还在栈中。所以 LOW[4] = 1。由于节点 6 已经弹栈， 边 (4, 6) 是指向非栈中节点的横叉边，因此不更新 LOW[4]。回溯返回到结点3，(3, 4) 为树枝边，所以 LOW[3] = LOW[4] = 1。

横叉边：从某个结点指向搜索树中另一个子树中的某结点的边 树枝边：DFS 时经过的边，即 DFS 搜索树上的边。

回溯到根结点 1，最后 DFS 到点 2。访问边 (2, 4)，此时点 4 还在栈中，所以 LOW[2] = DFN[4] = 5 返回 1 后，发现 DFN[1] = LOW[1]，所以我们就将栈中的点全部取出，组成一个强连通分量 {1, 3, 4, 2}。

至此，算法结束。我们通过一次 DFS ，求出了图中全部的三个强连通分量 {1, 3, 4, 2}，{5}，{6}。

可以发现，在 Tarjan 算法中，每个顶点都被访问了一次，且只进出一次栈，每条边也只被访问了一次，所以算法时间复杂度为 O(n + m)。