这个算法其实就是Tarjan算法的变异体，我们观察一下，只是它用第二个堆栈来辅助求出强连通分量的根，而不是Tarjan算法里面的indx[]和mlik[]数组。那么，我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。

我们使用类比方法，在Tarjan算法中，每次mlik[i]的修改都是由于环的出现(不然，mlik[i]的值不可能变小)，每次出现环，在这个环里面只剩下一个mlik[i]没有被改变(深度最低的那个)，或者全部被改变，因为那个深度最低的节点在另一个环内。那么Gabow算法中的第二堆栈变化就是删除构成环的节点，只剩深度最低的节点，或者全部删除，这个过程是通过出栈来实现，因为深度最低的那个顶点一定比前面的先访问，那么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问:为什么弹出的都是同一个强连通分量?因为在这个节点访问之前，能够构成强连通分量的那些节点已经被弹出了，这个对Tarjan算法有了解的都应该清楚，那么Tarjan算法中的判断根我们用什么来代替呢?想想，其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。

现 在，你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现，但是，Gabow算法更精妙，时间更少(不用频繁更新mlik[])。

Gabow_Algorithm:

步骤1:

找一个没有被访问过的节点v，goto step2(v)。否则，算法结束。

步骤2(v):

将v压入堆栈stk1[]和stk2[]

对于v所有的邻接顶点u:

1) 如果没有访问过，则step2(u)

2) 如果访问过，但没有删除，维护stk2[](处理环的过程)

如果stk2[]的顶元素==v，那么输出相应的强连通分量