Tarjan - Tarjan算法
问题
用Tarjan算法求有向图的所有强连通分支。
解法
Tarjan算法通过定义强连通分支的根节点，来求出有向图的所有强连通分支。有向图中一个强连通分支中的根节点是该强连通分支中下标最小的顶点，也是该强连通分支中所有顶点通过DFS能够搜索到的下标最小的顶点。
设为顶点下标，为该顶点所属强连通分支的根节点下标，显然属于同一个强连通分支的所有顶点值相等。同一个强连通分支中的所有顶点满足，强连通分支的根节点满足，其他顶点则满足。
Tarjan算法按照以下几步操作：
初始时设任意顶点的强连通分支的根节点指向自己，即，Tarjan的根节点和Kosaraju中并查集的父节点含义完全相同，因此也用父指针表示；
用DFS算法搜索有向图的所有顶点，得到每个顶点的，并按照搜索顺序将顶点推入堆栈（先入后出）；
从堆栈中依次取出每个顶点（即逆序遍历DFS搜索到的所有顶点），判断其是否为根节点（）。若出栈顶点是根节点，则在之前出栈的且未分配到其他强连通分支的顶点（的顶点即为未分配的顶点），都属于以为根节点的强连通分支，设置；若出栈顶点不是根节点，则等待根节点，属于以为根节点的强连通分支；
该算法时间复杂度为。