摘要：在實際的測試中，算法的運行效率也比算法高左右。此外，該算法與求無向圖的雙連通分量割點橋的算法也有著很深的聯(lián)系。學習該算法，也有助于深入理解求雙連通分量的算法，兩者可以類比組合理解。固屬于同一連通分支。

參考資料
http://blog.csdn.net/acmmmm/a...
https://www.byvoid.com/blog/s...
http://blog.csdn.net/nothi/ar...

在教材中有向圖的強連通只提及了一種，其實還有另外兩個經(jīng)典的算法，因此做一個補充。

tarjan的過程就是dfs過程

對圖dfs一下，遍歷所有未遍歷過的點 ，會得到一個有向樹，顯然有向樹是沒有環(huán)的。

（注意搜過的點不會再搜） 則能產(chǎn)生環(huán)的只有 指向已經(jīng)遍歷過的點 的邊

只有紅色與綠色邊有可能產(chǎn)生環(huán)。
對于深搜過程，我們需要一個棧來保存當前所在路徑上的所有點（棧中所有點一定是有父子關系的）
再仔細觀察紅邊與綠邊，首先得到結論：紅邊不產(chǎn)生環(huán)，綠邊產(chǎn)生環(huán)

對于紅邊，連接的兩個點3、7沒有父子關系，這種邊稱為橫叉邊。
橫叉邊一定不產(chǎn)生環(huán)。

對于綠邊，連接的兩個點6、4是父子關系，這種邊稱為后向邊。
環(huán)一定由后向邊產(chǎn)生。

圖中除了黑色的樹枝邊，一定只有橫叉邊和后向邊（不存在其他種類的邊）

則以下考慮對于這兩種邊的處理和判斷：

Stack = {1,2,3}。3沒有多余的其他邊，因此3退棧，把3作為一個強連通分量

再次深搜：

此時棧 Stack = {1,2,7}
發(fā)現(xiàn)紅邊指向了已經(jīng)遍歷過的點3 => 是上述的2種邊之一
而3不在棧中
=> 3點與7點無父子關系
=> 該邊為橫叉邊
=> 采取無視法。

繼而7點退棧 產(chǎn)生連通分量{7}
繼而2點退棧 產(chǎn)生連通分量{2}

再次深搜：

此時 Stack = {1,4,5,6}
發(fā)現(xiàn)綠邊指向了已經(jīng)遍歷過的點4 => 是上述的2種邊之一
而4在棧中
=> 4點與6點是父子關系
=> 該邊為后向邊
=> 4->6的路徑上的點都是環(huán)。

實際情況可能更復雜：

出現(xiàn)了大環(huán)套小環(huán)的情況，顯然我們認為最大環(huán)是一個強連通分量(即:{4,5,6,8} ）

因而我們需要強化一下dfs過程，增添幾個變量來記錄父節(jié)點和后向邊的情況

定義：

int dfn[N], low[N];

dfn[i] 表示 遍歷到 i 點時是第幾次dfs （有時也叫時間戳）

low[u] 表示 u 的子樹 能連接到 [棧中] 最上端的點 的dfn值(換句話說，也就是最小的dfn）

Stack stack 上述的棧
int BelongTo[N] 強連通分量的ID

通俗語言解讀：

dfn[i] 即我就是我，是數(shù)字不一樣的煙火。每個點的ID（不是強連通分量的ID，而是每個點自己的身份標識ID），按時間順序賦值。比如第一個尋訪的dfn的值為 1，第二個尋訪的DFN的值為 2，以此類推。可以通過比較大小來判斷是爸爸還是兒子。（是后向邊還是橫插邊？）

low[u] 如果是后向邊的話連到哪個爸爸？記錄下來爸爸的ID。

Stack 怎么判斷是不是后向邊呢？—>看在不在棧內。

Tarjan算法是基于對圖深度優(yōu)先搜索的算法，每個強連通分量為搜索樹中的一棵子樹。
搜索時，把當前搜索樹中未處理的節(jié)點加入一個堆棧，回溯時可以判斷棧頂?shù)綏Ｖ械墓?jié)點是否為一個強連通分量。

定義dfn(u)為節(jié)點u搜索的次序編號(時間戳)；
Low(u)為u或u的子樹能夠追溯到的最早的棧中節(jié)點的次序號。

由定義可以得出，

low(u)=min
{
    dfn(u),
    low(v),(u,v)為樹枝邊，u為v的父節(jié)點 //回溯時用
    dfn(v),(u,v)為指向棧中節(jié)點的后向邊(非橫叉邊) // 已訪問過時用。沒有想明白為什么是dfn(v)而不是low(v)?????????
}

當dfn(u)==low(u)時，以u為根的搜索子樹上所有節(jié)點是一個強連通分量。

原因

在算法開始的時候，我們把 i 圧入棧中。根據(jù) low[i] 和 dfn[i] 的定義我們知道，

如果 low[i] < dfn[i]，則以 i 為頂點的子樹中，有指向祖先的后向邊，則說明 i 和 i 的父親為在同一連通分支，也就是說留在棧中的元素都是和父結點在同一連通分支的。

如果 low[i] == dfn[i]，則 i 為頂點的子樹中沒有后向邊，那么由于 留在棧中的元素都是和父結點在同一連通分支的，我們可以知道，從棧頂?shù)皆?i 構成了一個連通分支。顯然，low[i]不可能小于dfn[i]

算法偽代碼如下

tarjan(u)
{
    dfn[u]=low[u]=++index                      // 為節(jié)點u設定次序編號和low初值
    stack.push(u)                              // 將節(jié)點u壓入棧中
    for each (u, v) in E                       // 枚舉每一條邊
        if (v is not visted)               // 如果節(jié)點v未被訪問過
            tarjan(v)                  // 繼續(xù)向下找
            Low[u] = min(low[u], low[v])
        else if (v in stack)                   // 如果節(jié)點v還在棧內
            Low[u] = min(low[u], dfn[v])
    if (dfn[u] == low[u])                      // 如果節(jié)點u是強連通分量的根
        repeat
            v = stack.pop                  // 將v退棧，為該強連通分量中一個頂點
            print v
        until (u== v)
}

復雜度

時間：O(N+M)

與Trajan算法相比，Kosaraju算法可能會稍微更直觀一些。但是Tarjan只用對原圖進行一次DFS，不用建立逆圖，更簡潔。在實際的測試中，Tarjan算法的運行效率也比Kosaraju算法高30%左右。此外，該Tarjan算法與求無向圖的雙連通分量(割點、橋)的Tarjan算法也有著很深的聯(lián)系。學習該Tarjan算法，也有助于深入理解求雙連通分量的Tarjan算法，兩者可以類比、組合理解。

public class Tarjan {
    private int[] id; // 強連通ID
    private int index_id = 0; // 強連通ID計數(shù)器
    private int[] dfn, low; //時間戳計數(shù)器
    private int index_dfn = 1; //時間戳初始化時默認為0。因此從1開始賦值，以區(qū)別是否訪問過。
    private Stack stack= new Stack();
    private boolean[] onStack;
    
    public Tarjan(Digraph G) {
        onStack = new boolean[G.V()];
        id = new int[G.V()];
        dfn = new int[G.V()];
        low = new int[G.V()];

        for (int s = 0; s < G.V(); s++)
            if (dfn[s]==0) {
                tarjan(G, s);
                index_id++;
            }
    }

    private void tarjan(Digraph G, int u) {
        stack.push(u); //壓入棧
        onStack[u] = true; //方便之后判斷
        dfn[u] = low[u] = ++index_dfn; //時間戳賦值，并表示訪問過了
        for (int w : G.adj(u)) {
            if (dfn[w] == 0) { //若w未被訪問過
                tarjan(G, w); //繼續(xù)深搜
                low[u] = Math.min(low[w], low[u]); //回溯，當前點u 選取包括自己的子樹中最小的low值
            } else if (onStack[w] && dfn[w]
簡單證明
首先，這邊再重復一下什么是后向邊：就是在深度優(yōu)先搜索中，子孫指向祖先的邊。
在一棵深度優(yōu)先搜索樹中，對于結點v, 和其父親結點u而言，u,v 屬于同一個強連通分支的充分必要條件是  
以ｖ為根的子樹中，有一條后向邊指向u或者u的祖先。
1、必要性
如果 u, v 屬于同一個強連通分支則必定存在一條 u -> v 的路徑和一條 v -> u的路徑。
合并兩條則有 u->v->v1->v2->..vn->u, 若頂點v1到vn都是v 的子孫,則有 vn->u這樣一條后向邊。
如果v1到vn 不全是vn的子孫，則必定有一個是u的祖先，我們不妨設vi為u的祖先，則有一條后向邊 V[i-1] ->v[i]。
2、充分性
我們設 u1->u2->u3..->un->u->v->v1->v2..->vn。
我們假設后向邊vn指向ui則有這樣一個環(huán)：u[i]->u[i+1]...->u->v->v1->v2..->v[n-1]->v[n]->u[i]。
易知，有一條u->v的路徑，同時有v->u的路徑。固u,v屬于同一連通分支。