Kosaraju算法
算法思路
基本思路：這個算法可以說是最容易理解，最通用的算法，其比較關鍵的部分是同時應用了原圖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，否則算法結束。
實現代碼
#include
usingnamespacestd;
constintMAXN=110;
typedefintAdjTable[MAXN];//鄰接表類型
intn;
boolflag[MAXN];//訪問标志數組
intbelg[MAXN];//存儲強連通分量,其中belg[i]表示頂點i屬于第belg[i]個強連通分量
intnumb[MAXN];//結束時間标記,其中numb[i]表示離開時間為i的頂點
AdjTableadj[MAXN],radj[MAXN];//鄰接表,逆鄰接表
//用于第一次深搜,求得numb[1..n]的值
voidVisitOne(intcur,int&sig)
{
flag[cur]=true;
for(inti=1;i<=adj[cur][0];++i)
{if(false==flag[adj[cur][i]])
{VisitOne(adj[cur][i],sig);}}
numb[++sig]=cur;}
//用于第二次深搜,求得belg[1..n]的值
voidVisitTwo(intcur,intsig)
{flag[cur]=true;
belg[cur]=sig;
for(inti=1;i<=radj[cur][0];++i)
{if(false==flag[radj[cur][i]])
{VisitTwo(radj[cur][i],sig);}}}
//Kosaraju算法,返回為強連通分量個數
intKosaraju_StronglyConnectedComponent()
{inti,sig;//第一次深搜
memset(flag+1,0,sizeof(bool)*n);
for(sig=0,i=1;i<=n;++i)
{if(false==flag[i]){VisitOne(i,sig);}}//第二次深搜
memset(flag+1,0,sizeof(bool)*n);
for(sig=0,i=n;i>0;--i)
{if(false==flag[numb[i]])
{VisitTwo(numb[i],++sig);}}
returnsig;}
Tarjan算法
Tarjan算法思路
這個算法思路不難理解，由開篇第一句話可知，任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那麼其實，我們隻要确定每個強連通分量的子樹的根，然後根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。那麼剩下的問題就隻剩下如何确定強連通分量的根和如何從最低層開始拿出強連通分量了。
那麼如何确定強連通分量的根，在這裡我們維護兩個數組，一個是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]更小的值。
至于如何拿出強連通分量，這個其實很簡單，如果當前節點為一個強連通分量的根，那麼它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍曆的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。現在知道如何拿出了強連通分量了吧？是的，因為當前節點是這個強連通分量中最先被壓人堆棧的，那麼在當前節點以後壓入堆棧的并且仍在堆棧中的節點都屬于這個強連通分量。
當然有人會問真的嗎？假設一個節點在當前節點壓入堆棧以後壓入并且還存在，同時它不屬于該強連通分量，那麼它一定屬于另一個強連通分量，但當前節點是它的根的祖宗，那麼這個強連通分量應該在此之前已經被拿出。現在沒有疑問了吧，那麼算法介紹就完了。
Tarjan僞代碼
Tarjan_Algorithm:
step1:找一個沒有被訪問過的節點v，gotostep2(v)。否則，算法結束。
step2(v):初始化indx[v]和mlik[v]對于v所有的鄰接頂點u：
1)如果沒有訪問過，則step2(u),同時維護mlik[v]
2)如果訪問過，但沒有删除，維護mlik[v]
如果indx[v]==mlik[v]，那麼輸出相應的強連通分量
Gabow算法思路
這個算法其實就是Tarjan算法的變異體，我們觀察一下，隻是它用第二個堆棧來輔助求出強連通分量的根，而不是Tarjan算法裡面的indx[]和mlik[]數組。那麼，我們說一下如何使用第二個堆棧來輔助求出強連通分量的根。
我們使用類比方法，在Tarjan算法中，每次mlik[i]的修改都是由于環的出現(不然，mlik[i]的值不可能變小)，每次出現環，在這個環裡面隻剩下一個mlik[i]沒有被改變(深度最低的那個)，或者全部被改變，因為那個深度最低的節點在另一個環内。那麼Gabow算法中的第二堆棧變化就是删除構成環的節點，隻剩深度最低的節點，或者全部删除，這個過程是通過出棧來實現，因為深度最低的那個頂點一定比前面的先訪問，那麼隻要出棧一直到棧頂那個頂點的訪問時間不大于深度最低的那個頂點。
其中每個被彈出的節點屬于同一個強連通分量。那有人會問：為什麼彈出的都是同一個強連通分量？因為在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan算法有了解的都應該清楚，那麼Tarjan算法中的判斷根我們用什麼來代替呢？想想，其實就是看看第二個堆棧的頂元素是不是當前頂點就可以了。
現在，你應該明白其實Tarjan算法和Gabow算法其實是同一個思想的不同實現，但是，Gabow算法更精妙，時間更少(不用頻繁更新mlik[])。
僞代碼
Gabow_Algorithm:
步驟1:
找一個沒有被訪問過的節點v，gotostep2(v)。否則，算法結束。
步驟2(v):
将v壓入堆棧stk1[]和stk2[]
對于v所有的鄰接頂點u：
1)如果沒有訪問過，則step2(u)
2)如果訪問過，但沒有删除，維護stk2[](處理環的過程)
如果stk2[]的頂元素==v，那麼輸出相應的強連通分量
總結
Kosaraju算法的第二次深搜隐藏了一個拓撲性質，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它們不具有拓撲性質。Tarjan算法用堆棧和标記，Gabow用兩個堆棧（其中一個堆棧的實質是代替了Tarjan算法的标記部分）來代替Kosaraju算法的第二次深搜，所以隻用一次深搜，效率比Kosaraju算法要高。
