在最近學(xué)習(xí)中遇到了幾次題解使用Tarjan的情況，便查了一些資料。
算法簡介
一種由Robert Tarjan提出的求解有向圖強(qiáng)連通分量的線性時(shí)間的算法脖隶。
前置解釋
1.如果有向圖兩個(gè)頂點(diǎn)可以相互通達(dá)，則稱兩個(gè)頂點(diǎn)強(qiáng)連通(strongly connected)。
2.如果有向圖G的每兩個(gè)頂點(diǎn)都強(qiáng)連通库快，稱G是一個(gè)強(qiáng)連通圖。
3.有向圖的極大強(qiáng)連通子圖钥顽，稱為強(qiáng)連通分量(strongly connected components)义屏。
舉個(gè)例子
在圖1中，圖{1,2,3,4}為一個(gè)強(qiáng)連通分量蜂大，因?yàn)?闽铐，2，3奶浦，4兄墅，都可以兩兩到達(dá)，當(dāng)然｛5｝澳叉，｛6｝也是兩個(gè)強(qiáng)連通分量隙咸。
而我們Tarjan算法的目的就是求解有向圖的強(qiáng)連通分量
Tarjan算法是基于對圖深度優(yōu)先搜索的算法沐悦，每個(gè)強(qiáng)連通分量為搜索樹中的一棵子樹。搜索時(shí)扎瓶，把當(dāng)前搜索樹中未處理的節(jié)點(diǎn)加入一個(gè)堆棧所踊，回溯時(shí)可以判斷棧頂?shù)綏Ｖ械墓?jié)點(diǎn)是否為一個(gè)強(qiáng)連通分量。
圖解模擬有如下定義概荷。
DFN[ i ] : 在DFS中該節(jié)點(diǎn)被搜索的次序(時(shí)間戳)
LOW[ i ] : 為i或i的子樹能夠追溯到的最早的棧中節(jié)點(diǎn)的次序號
當(dāng)DFN[ i ]==LOW[ i ]時(shí)秕岛，為i或i的子樹可以構(gòu)成一個(gè)強(qiáng)連通分量。
以1號節(jié)點(diǎn)為Tarjan 算法的起始點(diǎn)误证，以DFS序開始搜
順次DFS搜到節(jié)點(diǎn)6继薛，同時(shí)更新DFN,LOW
開始回溯，發(fā)現(xiàn)LOW[ 5 ]==DFN[ 5 ] , LOW[ 6 ]==DFN[ 6 ] ,則{ 5 } , { 6 } 為兩個(gè)強(qiáng)連通分量愈捅。
拓展節(jié)點(diǎn)1 遏考， 發(fā)現(xiàn)1在棧中更新LOW[ 4 ]，LOW[ 3 ] 的值為1
回溯節(jié)點(diǎn)1蓝谨，拓展節(jié)點(diǎn)2
至此灌具，Tarjan Algorithm 結(jié)束，{1 , 2 , 3 , 4 } , { 5 } , { 6 } 為圖中的三個(gè)強(qiáng)連通分量譬巫。
時(shí)間復(fù)雜度
O（E+V）
每個(gè)頂點(diǎn)都被訪問了一次咖楣，且只進(jìn)出了一次堆棧，每條邊也只被訪問了一次
參考代碼
偽代碼
tarjan(u)
{
DFN[u]=Low[u]=++Index//為節(jié)點(diǎn)u設(shè)定次序編號和Low初值
Stack.push(u)//將節(jié)點(diǎn)u壓入棧中
for each(u,v) in E//枚舉每一條邊
if (visnotvisted)//如果節(jié)點(diǎn)v未被訪問過
tarjan(v)//繼續(xù)向下找
Low[u]=min(Low[u],Low[v])
else if (vinS)//如果節(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)
printv
until(u==v)
}
}
C++代碼
void tarjan(int x){
dfn[x]=low[x]=++tot;//入棧
sta[++num]=x;insta[x]=true;
for(int i=head[x];i;i=edge[i].next){
if(!dfn[edge[i].to]){
tarjan(edge[i].to);
low[x]=min(low[x],low[edge[i].to]);
}
else if(insta[edge[i].to])
low[x]=min(low[x],dfn[edge[i].to]);
}
if(low[x]==dfn[x]){
sa=0;
do{sa++;insta[sta[num--]]=false;}//彈棧
while(x!=sta[num+1]);
if(sa==2){puts("2");exit(0);}//到2就沒必要繼續(xù)了
if(sa>1)ans=min(ans,sa);//取最小值
}
}
以下列出參考的文章诱贿，感謝這些作者提供的文章。
1.Tarjan 算法&模板
2.P2661 信息傳遞 tarjan
3.百度百科-tarjan算法
