Kosaraju - Kosaraju算法
问题
用Kosaraju算法求有向图的所有强连通分支。
解法
首先用DFS搜索所有顶点，然后按照DFS逆序对每个顶点进行DFS。根据强连通分支的定义可知。逆序时任意顶点按照DFS搜索可以到达的顶点都和它属于同一强连通分支。Kosaraju算法使用并查集将顶点分配给不同的强连通分支。
Kosaraju算法分为步：
初始化空队列，该队列记录有向图中所有顶点的DFS顺序；
类似DFS和二叉树的后续遍历，遍历图所有顶点，对每个顶点进行搜索操作： 若顶点已被染红则跳过，否则将染红并加入队列； 选取的邻节点中未被染红的邻节点，递归进行相同的搜索操作，直到无法搜索到更多未被染红的顶点；
类似DFS和并查集算法，首先令队列中的任意顶点属于根节点为（即自己）的强连通分支，即设父指针。逆序遍历队列所有顶点，对每个顶点进行聚合： 若顶点存在则跳过，表示该顶点已经被分配到某个强连通分支； 选取的邻节点中满足的邻节点，将分配给以为根节点的强连通分支，即；
第步结束后，每个顶点都被分配给某个强连通分支。查询某两个顶点是否属于同一个强连通分支，判断是否成立即可，同一强连通分支中的所有顶点的父节点相同，最终所有顶点都被分配到某个强连通分支。
下图演示有向图的搜索操作和分配操作：
上图进行DFS搜索后，得到的队列为，逆序为。第步的DFS搜索过程如下图：
按照逆序DFS遍历所有顶点，得到两个强连通分支和：
该算法时间复杂度为。