這個(gè)算法思路不難理解，由開(kāi)篇第一句話可知，任何一個(gè)強(qiáng)連通分量，必定是對(duì)原圖的深度優(yōu)先搜索樹(shù)的子樹(shù)。那么其實(shí)，我們只要確定每個(gè)強(qiáng)連通分量的子樹(shù)的根，然后根據(jù)這些根從樹(shù)的最低層開(kāi)始，一個(gè)一個(gè)的拿出強(qiáng)連通分量即可。那么剩下的問(wèn)題就只剩下如何確定強(qiáng)連通分量的根和如何從最低層開(kāi)始拿出強(qiáng)連通分量了。

那么如何確定強(qiáng)連通分量的根，在這里我們維護(hù)兩個(gè)數(shù)組，一個(gè)是indx[1..n]，一個(gè)是mlik[1..n]，其中indx[i]表示頂點(diǎn)i開(kāi)始訪問(wèn)時(shí)間，mlik[i]為與頂點(diǎn)i鄰接的頂點(diǎn)未刪除頂點(diǎn)j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過(guò)程中，如果發(fā)現(xiàn)mlik[i]==indx[i]那么，當(dāng)前頂點(diǎn)就是一個(gè)強(qiáng)連通分量的根，為什么呢?因?yàn)槿绻皇菑?qiáng)連通分量的根，那么它一定是屬于另一個(gè)強(qiáng)連通分量，而且它的根是當(dāng)前頂點(diǎn)的祖宗，那么存在包含當(dāng)前頂點(diǎn)的到其祖宗的回路，可知mlik[i]一定被更改為一個(gè)比indx[i]更小的值。

至于如何拿出強(qiáng)連通分量，這個(gè)其實(shí)很簡(jiǎn)單，如果當(dāng)前節(jié)點(diǎn)為一個(gè)強(qiáng)連通分量的根，那么它的強(qiáng)連通分量一定是以該根為根節(jié)點(diǎn)的(剩下節(jié)點(diǎn))子樹(shù)。在深度優(yōu)先遍歷的時(shí)候維護(hù)一個(gè)堆棧，每次訪問(wèn)一個(gè)新節(jié)點(diǎn)，就壓入堆棧。現(xiàn) 在知道如何拿出了強(qiáng)連通分量了吧?是的，因?yàn)楫?dāng)前節(jié)點(diǎn)是這個(gè)強(qiáng)連通分量中最先被壓入堆棧的，那么在當(dāng)前節(jié)點(diǎn)以后壓入堆棧的并且仍在堆棧中的節(jié)點(diǎn)都屬于這個(gè)強(qiáng)連通分量。當(dāng)然有人會(huì)問(wèn)真的嗎?假設(shè)一個(gè)節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)壓入堆棧以后壓入并且還存在，同時(shí)它不屬于該強(qiáng)連通分量，那么它一定屬于另一個(gè)強(qiáng)連通分量，但當(dāng)前節(jié)點(diǎn)是它的根的祖宗，那么這個(gè)強(qiáng)連通分量應(yīng)該在此之前已經(jīng)被拿出。現(xiàn) 在沒(méi)有疑問(wèn)了吧，那么算法介紹就完了。

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

做一個(gè)總結(jié):Kosaraju算法的第二次深搜隱藏了一個(gè)拓?fù)湫再|(zhì)，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它們不具有拓?fù)湫再|(zhì)。Tarjan算法用堆棧和標(biāo)記，Gabow用兩個(gè)堆棧(其中一個(gè)堆棧的實(shí)質(zhì)是代替了Tarjan算法的標(biāo)記部分)來(lái)代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法要高。

這個(gè)算法可以說(shuō)是最容易理解，最通用的算法，其比較關(guān)鍵的部分是同時(shí)應(yīng)用了原圖G和反圖GT。步驟1:先用對(duì)原圖G進(jìn)行深搜形成森林(樹(shù))，步驟2:然后任選一棵樹(shù)對(duì)其進(jìn)行深搜(注意這次深搜節(jié)點(diǎn)A能往子節(jié)點(diǎn)B走的要求是EAB存在于反圖GT)，能遍歷到的頂點(diǎn)就是一個(gè)強(qiáng)連通分量。余下部分和原來(lái)的森林一起組成一個(gè)新的森林，繼續(xù)步驟2直到 沒(méi)有頂點(diǎn)為止。

改進(jìn)思路:

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

隱藏性質(zhì):

分析到這里，我們已經(jīng)知道怎么求強(qiáng)連通分量了。但是，大家有沒(méi)有注意到我們?cè)诘诙紊钏堰x擇樹(shù)的順序有一個(gè)特點(diǎn)呢?如果在看上述思路的時(shí)候，你的腦子在思考，相信你已經(jīng)知道了!!!它就是:如果我們把求出來(lái)的每個(gè)強(qiáng)連通分量收縮成一個(gè)點(diǎn)，并且用求出每個(gè)強(qiáng)連通分量的順序來(lái)標(biāo)記收縮后的節(jié)點(diǎn)，那么這個(gè)順序其實(shí)就是強(qiáng)連通分量收縮成點(diǎn)后形成的有向無(wú)環(huán)圖的拓?fù)湫蛄小槭裁茨?首先，應(yīng)該明確搜索后的圖一定是有向無(wú)環(huán)圖呢?廢話，如果還有環(huán)，那么環(huán)上的頂點(diǎn)對(duì)應(yīng)的所有原來(lái)圖上的頂點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量，而不是構(gòu)成環(huán)上那么多點(diǎn)對(duì)應(yīng)的獨(dú)自的強(qiáng)連通分量了。然后就是為什么是拓?fù)湫蛄校覀冊(cè)诟倪M(jìn)分析的時(shí)候，不是先選的樹(shù)不會(huì)連通到其他樹(shù)上(對(duì)于反圖GT來(lái)說(shuō))，也就是后選的樹(shù)沒(méi)有連通到先選的樹(shù)，也即先出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)只能指向后出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)。那么拓?fù)湫蛄胁皇抢硭?dāng)然的嗎?這就是Kosaraju算法的一個(gè)隱藏性質(zhì)。

Kosaraju_Algorithm:

step1:對(duì)原圖G進(jìn)行深度優(yōu)先遍歷，記錄每個(gè)節(jié)點(diǎn)的離開(kāi)時(shí)間。

step2:選擇具有最晚離開(kāi)時(shí)間的頂點(diǎn)，對(duì)反圖GT進(jìn)行遍歷，刪除能夠遍歷到的頂點(diǎn)，這些頂點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量。

step3:如果還有頂點(diǎn)沒(méi)有刪除，繼續(xù)step2，否則算法結(jié)束。

C++

這個(gè)算法其實(shí)就是Tarjan算法的變異體，我們觀察一下，只是它用第二個(gè)堆棧來(lái)輔助求出強(qiáng)連通分量的根，而不是Tarjan算法里面的indx[]和mlik[]數(shù)組。那么，我們說(shuō)一下如何使用第二個(gè)堆棧來(lái)輔助求出強(qiáng)連通分量的根。

我們使用類比方法，在Tarjan算法中，每次mlik[i]的修改都是由于環(huán)的出現(xiàn)(不然，mlik[i]的值不可能變小)，每次出現(xiàn)環(huán)，在這個(gè)環(huán)里面只剩下一個(gè)mlik[i]沒(méi)有被改變(深度最低的那個(gè))，或者全部被改變，因?yàn)槟莻€(gè)深度最低的節(jié)點(diǎn)在另一個(gè)環(huán)內(nèi)。那么Gabow算法中的第二堆棧變化就是刪除構(gòu)成環(huán)的節(jié)點(diǎn)，只剩深度最低的節(jié)點(diǎn)，或者全部刪除，這個(gè)過(guò)程是通過(guò)出棧來(lái)實(shí)現(xiàn)，因?yàn)樯疃茸畹偷哪莻€(gè)頂點(diǎn)一定比前面的先訪問(wèn)，那么只要出棧一直到棧頂那個(gè)頂點(diǎn)的訪問(wèn)時(shí)間不大于深度最低的那個(gè)頂點(diǎn)。其中每個(gè)被彈出的節(jié)點(diǎn)屬于同一個(gè)強(qiáng)連通分量。那有人會(huì)問(wèn):為什么彈出的都是同一個(gè)強(qiáng)連通分量?因?yàn)樵谶@個(gè)節(jié)點(diǎn)訪問(wèn)之前，能夠構(gòu)成強(qiáng)連通分量的那些節(jié)點(diǎn)已經(jīng)被彈出了，這個(gè)對(duì)Tarjan算法有了解的都應(yīng)該清楚，那么Tarjan算法中的判斷根我們用什么來(lái)代替呢?想想，其實(shí)就是看看第二個(gè)堆棧的頂元素是不是當(dāng)前頂點(diǎn)就可以了。

現(xiàn) 在，你應(yīng)該明白其實(shí)Tarjan算法和Gabow算法其實(shí)是同一個(gè)思想的不同實(shí)現(xiàn)，但是，Gabow算法更精妙，時(shí)間更少(不用頻繁更新mlik[])。

Gabow_Algorithm:

步驟1:

找一個(gè)沒(méi)有被訪問(wèn)過(guò)的節(jié)點(diǎn)v，goto step2(v)。否則，算法結(jié)束。

步驟2(v):

將v壓入堆棧stk1[]和stk2[]

對(duì)于v所有的鄰接頂點(diǎn)u:

1) 如果沒(méi)有訪問(wèn)過(guò)，則step2(u)

2) 如果訪問(wèn)過(guò)，但沒(méi)有刪除，維護(hù)stk2[](處理環(huán)的過(guò)程)

如果stk2[]的頂元素==v，那么輸出相應(yīng)的強(qiáng)連通分量

有向圖的最大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。

強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即本身，非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。

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

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

Tarjan算法是基于對(duì)圖深度優(yōu)先搜索的算法，每個(gè)強(qiáng)連通分量為搜索樹(shù)中的一棵子樹(shù)。搜索時(shí)，把當(dāng)前搜索樹(shù)中未處理的節(jié)點(diǎn)加入一個(gè)堆棧，回溯時(shí)可以判斷棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量。

定義DFN(u)為節(jié)點(diǎn)u搜索的次序編號(hào)(時(shí)間戳)，Low(u)為u或u的子樹(shù)能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號(hào)。由定義可以得出，

Low(u)=Min{DFN(u),Low(v),(u,v)為樹(shù)枝邊，u為v的父節(jié)點(diǎn)

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

當(dāng)DFN(u)=Low(u)時(shí)，以u(píng)為根的搜索子樹(shù)上所有節(jié)點(diǎn)是一個(gè)強(qiáng)連通分量。

算法偽代碼如下

tarjan(u)

{

DFN[u]=Low[u]=++Index // 設(shè)定次序編號(hào)和Low初值

Stack.push(u) // 將節(jié)點(diǎn)u壓入棧中

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

if (v is not visted) // 如果節(jié)點(diǎn)v未被訪問(wèn)過(guò)

tarjan(v) // 繼續(xù)向下找

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

else if (v in S) // 如果節(jié)點(diǎn)v還在棧內(nèi)

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

if (DFN[u] == Low[u]) // 如果節(jié)點(diǎn)u是強(qiáng)連通分量的根

repeat

v = S.pop // 將v退棧，為該強(qiáng)連通分量中一個(gè)頂點(diǎn)

print v

until (u== v)

}

接下來(lái)是對(duì)算法流程的演示。

從節(jié)點(diǎn)1開(kāi)始DFS，把遍歷到的節(jié)點(diǎn)加入棧中。搜索到節(jié)點(diǎn)u=6時(shí)，DFN[6]=LOW[6]，找到了一個(gè)強(qiáng)連通分量。退棧到u=v為止，{6}為一個(gè)強(qiáng)連通分量。

返回節(jié)點(diǎn)5，發(fā)現(xiàn)DFN[5]=LOW[5]，退棧后{5}為一個(gè)強(qiáng)連通分量。

返回節(jié)點(diǎn)3，繼續(xù)搜索到節(jié)點(diǎn)4，把4加入堆棧。發(fā)現(xiàn)節(jié)點(diǎn)4像節(jié)點(diǎn)1的后向邊，節(jié)點(diǎn)1還在棧中，所以LOW[4]=1。節(jié)點(diǎn)6已經(jīng)出棧，不再訪問(wèn)6，返回3，(3,4)為樹(shù)枝邊，所以LOW[3]=LOW[4]=1。

繼續(xù)回到節(jié)點(diǎn)1，最后訪問(wèn)節(jié)點(diǎn)2。訪問(wèn)邊(2,4)，4還在棧中，所以LOW[2]=4。返回1后，發(fā)現(xiàn)DFN[1]=LOW[1]，把棧中節(jié)點(diǎn)全部取出，組成一個(gè)連通分量{1,3,4,2}。

至此，算法結(jié)束。經(jīng)過(guò)該算法，求出了圖中全部的三個(gè)強(qiáng)連通分量{1,3,4,2},{5},{6}。

可以發(fā)現(xiàn)，運(yùn)行Tarjan算法的過(guò)程中，每個(gè)頂點(diǎn)都被訪問(wèn)了一次，且只進(jìn)出了一次堆棧，每條邊也只被訪問(wèn)了一次，所以該算法的時(shí)間復(fù)雜度為O(N+M)。

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

求有向圖的強(qiáng)連通分量的Tarjan算法是以其發(fā)明者Robert Tarjan命名的。Robert Tarjan還發(fā)明了求雙連通分量的Tarjan算法，以及求最近公共祖先的離線Tarjan算法，在此對(duì)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);

}