關于tarjan，在下覺得這個算法從本質上是一種暴力求強連通分量的方法，但事實上這也是最有效的求強連通分量的方法之一，它對于處理各種強連通分量中奇怪問題，都可以直接轉化，所以比較通用和常見。

　　什么是tarjan

　　粗略的描述一下（詳細描述在百度里很詳細）

　　首先每個點都有時間戳和最小子樹戳。

　　時間戳的定義是這個點進行遞歸的時間，每新遞歸一次就增加，所以每個點的時間戳都不一樣，最小子樹戳的定義是當前點的子樹上節點中（包括它自己）時間戳的最小值。

　　它的基本方法是先把任意一個沒有tarjan過的點加入棧，然后把新加入的點當做一棵樹的根做處理，先把自己的時間戳和最小子樹戳設為自己，然后每次去找根的所鏈的每條邊，如果當前邊所接的目標節點沒有進行過tarjan，那就再tarjan遞歸處理，處理后，對比當前點最小子樹戳和所搜目標節點的最小子樹戳，取最小值；如果已經進行過tarjan，但是當前所搜到的目標節點不在棧里（也就是非當前點的來源節點），那么就什么也不做（因為只要這點進過tarjan就說明一定已經把它所處的強連通分量找過，并且找全，但你當前所處理的點是沒進過tarjan的，所以一定不和這種進過棧但當前不在棧的點屬于一個強連通分量）；最后一種情況進行過tarjan并且當前點再棧里，那么我們只需要對比當前點的最小子樹戳和目標節點的時間戳，取最小值。

　　如果搜索子樹的工作結束了，那么要判斷是否當前遞歸節點的時間戳和最小子樹戳相同：如果相同，那么從這個節點一直到棧頂都屬于同一個強連通分量，全部彈出；如果不同，結束當前遞歸。

先貼出tarjan的模板

1 void tarjan(int sb) 2 { 3 low[sb]=time[sb]=++T; 4 f[sb]=true; 5 stack[++ass]=sb; 6 for(int k=head[sb];k!=0;k=e[k].next) 7 { 8 if(!time[e[k].aim]) 9 { 10 tarjan(e[k].aim); 11 low[sb]=min(low[sb],low[e[k].aim]); 12 } 13 else if(f[e[k].aim])low[sb]=min(low[sb],time[e[k].aim]); 14 } 15 if(time[sb]==low[sb]) 16 { 17 f[sb]=false; 18 while(stack[ass]!=sb) 19 f[stack[ass--]]=false; 20 ass--; 21 } 22 }

?

在此提供一道tarjan裸題

　　codevs1332

　　在幻想鄉，上白澤慧音是以知識淵博聞名的老師。春雪異變導致人間之里的很多道路都被大雪堵塞，使有的學生不能順利地到達慧音所在的村莊。因此慧音決定換一個能夠聚集最多人數的村莊作為新的教學地點。人間之里由N個村莊（編號為1..N）和M條道路組成，道路分為兩種一種為單向通行的，一種為雙向通行的，分別用1和2來標記。如果存在由村莊A到達村莊B的通路，那么我們認為可以從村莊A到達村莊B，記為(A,B)。當(A,B)和(B,A)同時滿足時，我們認為A,B是絕對連通的，記為<A,B>。絕對連通區域是指一個村莊的集合，在這個集合中任意兩個村莊X,Y都滿足<X,Y>。現在你的任務是，找出最大的絕對連通區域，并將這個絕對連通區域的村莊按編號依次輸出。若存在兩個最大的，輸出字典序最小的，比如當存在1,3,4和2,5,6這兩個最大連通區域時，輸出的是1,3,4。

輸入描述?Input Description

第1行：兩個正整數N,M

第2..M+1行：每行三個正整數a,b,t, t = 1表示存在從村莊a到b的單向道路，t = 2表示村莊a,b之間存在雙向通行的道路。保證每條道路只出現一次。

輸出描述?Output Description

第1行： 1個整數，表示最大的絕對連通區域包含的村莊個數。

第2行：若干個整數，依次輸出最大的絕對連通區域所包含的村莊編號。

下面貼出手寫代碼

?

1 #include<cstdio> 2 struct shit{ 3 int aim; 4 int next; 5 bool use; 6 }e[50100]; 7 int max(int x,int y) 8 { 9 return x>y?x:y; 10 } 11 int min(int x,int y) 12 { 13 return x<y?x:y; 14 } 15 int point,head[5100],n,m,ass,cnt,stack[51000],low[51000],time[51000],ans[51000],a,b,num,T,cl2[51000],cl[10]; 16 bool f[51000]; 17 void fuck(int x,int y) 18 { 19 e[++point].aim=y; 20 e[point].next=head[x]; 21 head[x]=point; 22 } 23 void tarjan(int sb) 24 { 25 int x=ass; 26 stack[++ass]=sb; 27 f[sb]=true; 28 low[sb]=time[sb]=++T; 29 for(int k=head[sb];k!=0;k=e[k].next) 30 { 31 int c=e[k].aim; 32 if(!time[c]) 33 { 34 tarjan(c); 35 low[sb]=min(low[sb],low[c]); 36 } 37 else if(f[c])low[sb]=min(low[sb],time[c]); 38 } 39 if(low[sb]==time[sb]) 40 { 41 cnt++; 42 if(ass-x>=cl[0]) 43 { 44 cl[0]=ass-x; 45 cl[1]=cnt; 46 } 47 for(int i=1;i<=ass-x;i++) 48 { 49 cl2[stack[x+i]]=cnt; 50 f[stack[x+i]]=false; 51 } 52 ass=x; 53 } 54 return; 55 } 56 int main() 57 { 58 scanf("%d%d",&n,&m); 59 for(int i=1;i<=m;i++) 60 { 61 scanf("%d%d%d",&a,&b,&num); 62 if(num-1)fuck(b,a); 63 fuck(a,b); 64 } 65 for(int i=1;i<=n;i++) 66 if(!time[i])tarjan(i); 67 printf("%d\n",cl[0]); 68 point=0; 69 for(int i=1;i<=n;i++) 70 { 71 if(cl2[i]==cl[1])ans[++point]=i; 72 } 73 for(int i=1;i<=cl[0];i++) 74 { 75 printf("%d ",ans[i]); 76 } 77 return 0; 78 } View Code

?

?

?

?

轉載于:https://www.cnblogs.com/PencilWang/p/5868023.html

總結

以上是生活随笔為你收集整理的图论算法》关于tarjan算法两三事的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。