图的连通 —— Kosaraju 算法

与 Tarjan 类似，Kosaraju 算法也是用于求有向图的强连通分块，相较 Tarjan 算法其思想和实现都要简单不少。

Kosaraju 算法利用了一个显而易见的结论，即任意图与其逆图（翻转图中所有边所得图）拥有相同的强连通分量，该算法通过两次 DFS 遍历任意图与其逆图从而得到强连通分量。

举个例子，下图为一张连通图，其中方形为由多个节点组成的强连通分量，我们将它们看为一个整体，即图中一共有 4 个连通分量。

如果我们从 1 开始按节点编号顺序用 DFS 遍历这幅图，显然 1 次就能遍历完这幅图。如果我们从 11 开始按节点编号逆序用 DFS 遍历这幅图，则需要 4 次，即连通分块的个数。不难发现，如果我们按某一特定顺序用 DFS 遍历图，是可以每次只遍历一个连通分块的，但这个顺序显然不一定是节点编号顺序或逆序。

对于一张有向图，如果我们将其中同一连通分量中的节点视为一个整体，整幅图就变为一张有向无环图（DAG），因为任意两个连通分块之间一定无法相互到达，否则就可以视为一个更大的连通分块。我们知道拓扑排序可以处理 DAG 图，如果此时我们用拓扑排序的顺序（每次摘掉一个出度为零的节点）用 DFS 遍历图，就可以保证每次 DFS 只遍历一个连通分块。

这便是 Kosaraju 算法的基本思想，为了求出前文提到的节点顺序（以下简称为拓扑序）， 需要用到逆图。用 DFS 后序遍历逆图，将遍历的节点编号压入栈中，出栈顺序即为原图的拓排序。这不难证明，当 DFS 遍历到逆图的任意节点时，由于采用后序遍历，此时该节点的所有前驱节点都还未入栈，反过来当该节点出栈时，其所有前驱节点（在原图中为后继节点）都已经出栈，因此在原图中该节点的所有后继节点都已经遍历过，即任意节点出栈时其出度为零，所以出栈顺序即为拓扑序。

总的来说， Kosaraju 算法通过分别对原图与逆图进行 DFS 遍历得到图的连通分量，复杂度为 $O(n+m)$ ，与 Tarjan 相同，但由于需要建两幅图并遍历两遍，所以还是略逊于 Tarjan 算法，优点在于实现上比较简单（过于简单，因此实现代码略）。