Section-4 Connectivity 第4节 连通 - Tarjan Tarjan算法
Tarjan算法
问题：
用Tarjan算法求有向图(G)的强连通分支。
解法：
Tarjan算法定义了概念“强连通分支的根节点”。对有向图(G)中的节点(i)（范围为([0, n))），设置一个(low_i)值，表示从节点(i)出发进行DFS可以到达的所有节点中最小的节点标号。若节点(i)满足(low_i = i)，则该节点为强连通分支的根节点。
Tarjan算法分为(2)个步骤：
((1))对图(G)中的所有节点进行深度优先搜索，计算每个遍历到的节点的(low)值，并将其压入栈(Stack)中；
((2))依次从栈(Stack)中取出每个节点，并放入初始为空的集合(S)中。对于刚刚进入集合的节点(i)，若该节点为强连通分支的根节点，则当前集合(S)中的所有节点属于一个强连通分支。将它们全部取出作为一个强连通分支，将集合(S)清空，然后继续从栈(Stack)中取出节点，重复该操作。
节点的low值分别为([0_0, 0_1, 0_2, 0_3, 4_4, 5_5])，遍历顺序为([0, 1, 3, 2, 4, 5])，依次压入栈后得到(Stack = [5, 4, 2, 3, 1, 0])。
((1))将节点(5)放入集合(S = [5])，节点(low_5 = 5)，即节点(5)为强连通分支的根节点，因此([5])为一个强连通分支，将集合(S)清空；
((2))将节点(4)放入集合(S = [4])，节点(low_4 = 4)，即节点(4)为强连通分支的根节点，因此([4])为一个强连通分支，将集合(S)清空；
((3))将节点(2)放入集合(S = [2])，节点(low_2 = 0)，不做任何操作；
((4))将节点(3)放入集合(S = [2, 3])，节点(low_3 = 0)，不做任何操作；
((5))将节点(1)放入集合(S = [2, 3, 1])，节点(low_1 = 0)，不做任何操作；
((6))将节点(0)放入集合(S = [2, 3, 1, 0])，节点(low_0 = 0)，即节点(0)为强连通分支的根节点，因此([2, 3, 1, 0])为一个强连通分支，将集合(S)清空；
((7))栈(Stack)为空，算法结束。最终得到的强连通分支有(3)个，分别为([5])、([4])、([2, 3, 1, 0])；
在有(N)个节点的有向图(G)上运行Tarjan算法的时间复杂度为(O(N))。
Wikipedia: