這個算法其實就是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，那么輸出相應的強連通分量

這個算法思路不難理解，由開篇第一句話可知，任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那么其實，我們只要確定每個強連通分量的子樹的根，然后根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。那么剩下的問題就只剩下如何確定強連通分量的根和如何從最低層開始拿出強連通分量了。

那么如何確定強連通分量的根，在這里我們維護兩個數組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與頂點i鄰接的頂點未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發現mlik[i]==indx[i]那么，當前頂點就是一個強連通分量的根，為什么呢?因為如果它不是強連通分量的根，那么它一定是屬于另一個強連通分量，而且它的根是當前頂點的祖宗，那么存在包含當前頂點的到其祖宗的回路，可知mlik[i]一定被更改為一個比indx[i]更小的值。

至于如何拿出強連通分量，這個其實很簡單，如果當前節點為一個強連通分量的根，那么它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍歷的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。現 在知道如何拿出了強連通分量了吧?是的，因為當前節點是這個強連通分量中最先被壓入堆棧的，那么在當前節點以后壓入堆棧的并且仍在堆棧中的節點都屬于這個強連通分量。當然有人會問真的嗎?假設一個節點在當前節點壓入堆棧以后壓入并且還存在，同時它不屬于該強連通分量，那么它一定屬于另一個強連通分量，但當前節點是它的根的祖宗，那么這個強連通分量應該在此之前已經被拿出。現 在沒有疑問了吧，那么算法介紹就完了。

由于不同人編輯而注明，代碼中數組dfn為上述indx，low為mlik

這個算法可以說是最容易理解，最通用的算法，其比較關鍵的部分是同時應用了原圖G和反圖GT。步驟1:先用對原圖G進行深搜形成森林(樹)，步驟2:然后任選一棵樹對其進行深搜(注意這次深搜節點A能往子節點B走的要求是EAB存在于反圖GT)，能遍歷到的頂點就是一個強連通分量。余下部分和原來的森林一起組成一個新的森林，繼續步驟2直到 沒有頂點為止。

改進思路:

當然，基本思路實現起來是比較麻煩的(因為步驟2每次對一棵樹進行深搜時，可能深搜到其他樹上去，這是不允許的，強連通分量只能存在單棵樹中(由開篇第一句話可知))，我們當然不這么做，我們可以巧妙的選擇第二深搜選擇的樹的順序，使其不可能深搜到其他樹上去。想象一下，如果步驟2是從森林里選擇樹，那么哪個樹是不連通(對于GT來說)到其他樹上的呢?就是最后遍歷出來的樹，它的根節點在步驟1的遍歷中離開時間最晚，而且可知它也是該樹中離開時間最晚的那個節點。這給我們提供了很好的選擇，在第一次深搜遍歷時，記錄時間i離開的頂點j，即numb[i]=j。那么，我們每次只需找到沒有找過的頂點中具有最晚離開時間的頂點直接深搜(對于GT來說)就可以了。每次深搜都得到一個強連通分量。

隱藏性質:

分析到這里，我們已經知道怎么求強連通分量了。但是，大家有沒有注意到我們在第二次深搜選擇樹的順序有一個特點呢?如果在看上述思路的時候，你的腦子在思考，相信你已經知道了!!!它就是:如果我們把求出來的每個強連通分量收縮成一個點，并且用求出每個強連通分量的順序來標記收縮后的節點，那么這個順序其實就是強連通分量收縮成點后形成的有向無環圖的拓撲序列。為什么呢?首先，應該明確搜索后的圖一定是有向無環圖呢?廢話，如果還有環，那么環上的頂點對應的所有原來圖上的頂點構成一個強連通分量，而不是構成環上那么多點對應的獨自的強連通分量了。然后就是為什么是拓撲序列，我們在改進分析的時候，不是先選的樹不會連通到其他樹上(對于反圖GT來說)，也就是后選的樹沒有連通到先選的樹，也即先出現的強連通分量收縮的點只能指向后出現的強連通分量收縮的點。那么拓撲序列不是理所當然的嗎?這就是Kosaraju算法的一個隱藏性質。

Kosaraju_Algorithm:

step1:對原圖G進行深度優先遍歷，記錄每個節點的離開時間。

step2:選擇具有最晚離開時間的頂點，對反圖GT進行遍歷，刪除能夠遍歷到的頂點，這些頂點構成一個強連通分量。

step3:如果還有頂點沒有刪除，繼續step2，否則算法結束。

C++

做一個總結:Kosaraju算法的第二次深搜隱藏了一個拓撲性質，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它們不具有拓撲性質。Tarjan算法用堆棧和標記，Gabow用兩個堆棧(其中一個堆棧的實質是代替了Tarjan算法的標記部分)來代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法要高。

有向圖的最大強連通子圖稱為該有向圖的強連通分量。

強連通圖只有一個強連通分量，即本身，非強連通圖有多個強連通分量。

任何連通圖的連通分量只有一個，即為其本身。

直接根據定義，用雙向遍歷取交集的方法求強連通分量，時間復雜度為O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法，兩者的時間復雜度都是O(N+M)。本文介紹的是Tarjan算法。

Tarjan算法是基于對圖深度優先搜索的算法，每個強連通分量為搜索樹中的一棵子樹。搜索時，把當前搜索樹中未處理的節點加入一個堆棧，回溯時可以判斷棧頂到棧中的節點是否為一個強連通分量。

定義DFN(u)為節點u搜索的次序編號(時間戳)，Low(u)為u或u的子樹能夠追溯到的最早的棧中節點的次序號。由定義可以得出，

Low(u)=Min{DFN(u),Low(v),(u,v)為樹枝邊，u為v的父節點

DFN(v),(u,v)為指向棧中節點的后向邊(非橫叉邊)}

當DFN(u)=Low(u)時，以u為根的搜索子樹上所有節點是一個強連通分量。

算法偽代碼如下

tarjan(u)

{

DFN[u]=Low[u]=++Index // 設定次序編號和Low初值

Stack.push(u) // 將節點u壓入棧中

for each (u, v) in E // 枚舉每一條邊

if (v is not visted) // 如果節點v未被訪問過

tarjan(v) // 繼續向下找

Low[u] = min(Low[u], Low[v])

else if (v in S) // 如果節點v還在棧內

Low[u] = min(Low[u], DFN[v])

if (DFN[u] == Low[u]) // 如果節點u是強連通分量的根

repeat

v = S.pop // 將v退棧，為該強連通分量中一個頂點

print v

until (u== v)

}

接下來是對算法流程的演示。

從節點1開始DFS，把遍歷到的節點加入棧中。搜索到節點u=6時，DFN[6]=LOW[6]，找到了一個強連通分量。退棧到u=v為止，{6}為一個強連通分量。

返回節點5，發現DFN[5]=LOW[5]，退棧后{5}為一個強連通分量。

返回節點3，繼續搜索到節點4，把4加入堆棧。發現節點4像節點1的后向邊，節點1還在棧中，所以LOW[4]=1。節點6已經出棧，不再訪問6，返回3，(3,4)為樹枝邊，所以LOW[3]=LOW[4]=1。

繼續回到節點1，最后訪問節點2。訪問邊(2,4)，4還在棧中，所以LOW[2]=4。返回1后，發現DFN[1]=LOW[1]，把棧中節點全部取出，組成一個連通分量{1,3,4,2}。

至此，算法結束。經過該算法，求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。

可以發現，運行Tarjan算法的過程中，每個頂點都被訪問了一次，且只進出了一次堆棧，每條邊也只被訪問了一次，所以該算法的時間復雜度為O(N+M)。

求有向圖的強連通分量還有一個強有力的算法，為Kosaraju算法。Kosaraju是基于對有向圖及其逆圖兩次DFS的方法，其時間復雜度也是 O(N+M)。與Trajan算法相比，Kosaraju算法可能會稍微更直觀一些。但是Tarjan只用對原圖進行一次DFS，不用建立逆圖，更簡潔。 在實際的測試中，Tarjan算法的運行效率也比Kosaraju算法高30%左右。此外，該Tarjan算法與求無向圖的雙連通分量(割點、橋)的Tarjan算法也有著很深的聯系。學習該Tarjan算法，也有助于深入理解求雙連通分量的Tarjan算法，兩者可以類比、組合理解。

求有向圖的強連通分量的Tarjan算法是以其發明者Robert Tarjan命名的。Robert Tarjan還發明了求雙連通分量的Tarjan算法，以及求最近公共祖先的離線Tarjan算法，在此對Tarjan表示崇高的敬意。

void tarjan(int i)

{

int j;

DFN=LOW=++Dindex;

instack=true;

Stap[++Stop]=i;

for (edge *e=V;e;e=e->next)

{

j=e->t;

if (!DFN[j])

{

tarjan(j);

if (LOW[j]<LOW)

LOW=LOW[j];

}

else if (instack[j] && DFN[j]<LOW)

LOW=DFN[j];

}

if (DFN==LOW)

{

Bcnt++;

do

{

j=Stap[Stop--];

instack[j]=false;

Belong[j]=Bcnt;

}

while (j!=i);

}

}

void solve()

{

int i;

Stop=Bcnt=Dindex=0;

memset(DFN,0,sizeof(DFN));

for (i=1;i<=N;i++)

if (!DFN)

tarjan(i);

}