Tarjan算法：

　 這是SCC問題的第一個算法，由Tarjan于1972年提出。算法仍然借助DFS，但它并不依靠遍歷順序來把不同的SCC分離到不同的DFS樹中，而是讓多個SCC并存于同一個DFS樹中，用某種手段把他們分開。考慮一個強分量C，設其中第一個被發現的點為x，由白路徑定理，C中其他點都是x的后代。我們希望在x訪問完成時立刻輸出C。(注意這里是一個嚴格的數學描述)。這樣，就可以在同一棵DFS樹中區分開所有的SCC了。因此問題的關鍵是：如何判斷一個點是否為SCC中最先被發現的點。
　
　   如圖。假設我們正在判斷u是否為某SCC中第一個被發現的節點。如果我們發現從u的兒子出發可以到達u的祖先w,顯然u\v\w在同一個SCC中，因此u不是該SCC第一個被發現的節點。如果從v出現最多只能到u，那么u是該SCC中第一個被發現的節點（也許有同學會問，若所有子節點不能到達u本身，何以能說明u是和子樹強聯通的？其實由于DFS的特點，若這樣的情況出現，實際上在u的子樹上已經完成了一個強分量的尋找，u此時是只到它本身的“第一個”被發現節點，原書的描述是嚴格和歸納的）。這樣，問題轉化為求：一個點u最遠能到達的祖先的d值。注意這里的“到達”可以通過后向邊或交叉邊，但是前提是只能通過棧里面的點而不是已經確定SCC編號的其他點。圖中實線表示一條邊，虛線表示一條或多條邊。


      定義low[u]為u及其后代能追溯到的最早祖先v的發現時間戳pre[v]，我們可以在計算low函數的同時完成SCC的計算，low函數的遞推方法如下：
      利用全局棧_sta保存當前SCC中的節點（注意棧中節點形成樹而不一定是鏈），cnt為開發當前點u的時間戳，scnt為強分量編號器，id[]為強分量編號數組。

      原始的Tarjan算法遞推方式為：如果 pre[w]<pre[u]且w在棧中，則low[u]=min{pre[w],low[u]}，注意后一個限制是為了保證w不是在另一個已經發現的SCC中。下面的代碼更簡潔，在標記強分量后，只需要將low[w]設為最大值，表明它不再是任何點的祖先，那么w就不會被其他強分量吸收了，想想為什么。

 1void dfs-scc(int u){
 2    int w,min;
 3    min=low[u]=pre[u]=cnt++;
 4     /**//* 初始化時間戳，low值，子節點最小祖先 為當前時間戳 */
 5     _sta.push(u);
 6     
 7     for each (u,w){
 8         if(pre[w]==-1) dfs-scc(w);
 9         /**//* 未開發節點 */
10         if( low[w]<min ) min=low[w];
11         /**//* 求出u所有兒子i最遠能到達的祖先 */
12     }
13     
14     if(min<low[u]){ low[u]=min; return ; }
15     /**//* 所有的兒子能到達的最遠祖先是u的祖先，因此u不是SCC
16         第一個被發現的節點，通過子節點，u應能到達這樣的第一個節點 */
17     do{
18         w=_sta.pop(w);
19         id[w]=scant;
20         low[w]=0x7fffffff; /**//* 鎖定low，保證w不會被其他強分量吸收 */
21     }while(w!=u)
22     /**//* 此時，u的所有子節點必能且最遠僅能到達u，他們溝通構成一個SCC */
23     scant++;
24}