1,在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖，稱為強連通分量(strongly connected component)。
2,下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達。{5},{6}也分別是兩個強連通分量。


3,Tarjan算法是基于對圖深度優先搜索的算法，每個強連通分量為搜索樹中的一棵子樹。搜索時，把當前搜索樹中未處理的節點加入一個堆棧，回溯時可以判斷棧頂到棧中的節點是否為一個強連通分量。
定義幾個關鍵數組:
int DFN[MAX]; //記錄節點u第一次被訪問時的步數
int LOW[MAX]; //記錄與節點u和u的子樹節點中最早的步數
接下來是對算法流程的演示。
從節點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已經出棧，(4,6)是橫叉邊，返回3，(3,4)為樹枝邊，所以LOW[3]=LOW[4]=1。


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


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

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

4,實例代碼:

Cpp代碼

1. #include<iostream> ??
2. #include<vector> ??
3. using ? namespace ?std; ??
4. ??
5. const ? int ?MAX=10001; ??
6. ??
7. int ?Stop; //棧中的元素個數 ??
8. int ?cnt; //記錄連通分量的個數 ??
9. int ?visitNum; //記錄遍歷的步數 ??
10. int ?DFN[MAX];? //記錄節點u第一次被訪問時的步數 ??
11. int ?LOW[MAX];? //記錄與節點u和u的子樹節點中最早的步數 ??
12. bool ?instack[MAX]; //記錄節點u是否在棧中 ??
13. int ?Stap[MAX]; //棧 ??
14. int ?Belong[MAX]; //記錄每個節點屬于的強連通分量編號 ??
15. ??
16. int ?N; //節點個數 ??
17. ??
18. vector< int >?tree[MAX]; ??
19. ??
20. void ?tarjan( int ?i) ??
21. { ??
22. ???? int ?j; ??
23. ????DFN[i]=LOW[i]=++visitNum; ??
24. ????instack[i]= true ; ??
25. ????Stap[++Stop]=i; //將當前節點壓入棧中 ??
26. ???? for ?(unsigned?k=0;k<tree[i].size();k++) ??
27. ????{ ??
28. ????????j=tree[i][k]; ??
29. ???????? if ?(!DFN[j])? //j還沒有被訪問過 ??
30. ????????{ ??
31. ????????????tarjan(j); ??
32. ???????????? //父節點是子節點的子節點 ??
33. ???????????? if ?(LOW[j]<LOW[i]) ??
34. ????????????????LOW[i]=LOW[j]; ??
35. ????????} ??
36. ???????? //與j相連,但是j已經被訪問過,且還在棧中 ??
37. ???????? //用子樹節點更新節點第一次出現的時間 ??
38. ???????? else ? if ?(instack[j]?&&?DFN[j]<LOW[i]) ??
39. ????????????LOW[i]=DFN[j]; ??
40. ????} ??
41. ???? //節點i是強連通分量的根 ??
42. ???? if ?(DFN[i]==LOW[i]) ??
43. ????{ ??
44. ????????cnt++; ??
45. ???????? //輸出找到的強連通分量 ??
46. ????????cout<< "連通分量" <<cnt<< ":?" ; ??
47. ???????? //退棧,直至找到根為止 ??
48. ???????? do ??
49. ????????{ ??
50. ????????????j=Stap[Stop--]; ??
51. ????????????instack[j]= false ; ??
52. ????????????cout<<j<< "?" ; ??
53. ????????????Belong[j]=cnt; ??
54. ????????} ??
55. ???????? while ?(j!=i); ??
56. ????????cout<<endl; ??
57. ????} ??
58. } ??
59. void ?solve() ??
60. { ??
61. ????Stop=cnt=visitNum=0; ??
62. ????memset(DFN,0, sizeof (DFN)); ??
63. ???? for ?( int ?i=1;i<=N;i++) ??
64. ???????? if ?(!DFN[i]) //有可能圖不是連通圖 ??
65. ????????????tarjan(i); ??
66. } ??
67. ??
68. int ?main() ??
69. { ??
70. ????N=6; ??
71. ????tree[1].push_back(3); ??
72. ????tree[1].push_back(2); ??
73. ????tree[2].push_back(4); ??
74. ????tree[3].push_back(5); ??
75. ????tree[3].push_back(4); ??
76. ????tree[4].push_back(1); ??
77. ????tree[4].push_back(6); ??
78. ????tree[5].push_back(6); ??
79. ????solve(); ??
80. ???? for ( int ?i=1;i<=N;i++) ??
81. ????????cout<<Belong[i]<< "?" ; ??
82. ????cout<<endl; ??
83. ???? return ?0; ??
84. }??

求有向圖的強連通分量(scc):Tarjan算法