今天介紹的算法名叫Tarjan，同樣是一個很奇怪的名字，奇怪就對了，這也是以人名命名的。和Kosaraju算法比起來，它除了名字更好記之外，另外一個優點是它只需要一次遞歸，雖然算法的復雜度是一樣的，但是常數要小一些。它的知名度也更高，在競賽當中經常出現。

先給大家提個醒，相比于Kosaraju算法，Tarjan算法更難理解一些。所以如果你看完本文沒有搞明白的話，建議可以閱讀一下上一篇文章。這兩個算法的效果和復雜度都是一樣的，其實學會一個就可以，沒必要死磕。

算法框架

我們來思考一個問題，對于強連通分量分解的算法來說，它的核心原理是什么?

如果你看過我們之前的文章，那么這個問題對你來說應該不難回答。既然是強連通分量，意味著分量當中每個點都可以互相連通。所以我們很容易可以想到，我們可以從一個點出發，找到一個回路讓它再回到起點。這樣途中經過的點就都是強連通分量的一部分。

但是這樣會有一個問題，就是需要保證強連通分量當中的每個點都被遍歷到，不能有遺漏。針對這個問題我們也可以想到解法，比如可以用搜索算法去搜索它所有能夠達到的點和所有的路徑。但是這樣一來，我們又會遇到另外一個問題。這個問題就是強連通分量之間的連通問題。

我們來看個例子：

在上面這張圖當中如果我們從點1出發，我們可以達到圖中的每一個點。但是我們會發現1，2，3是一個強連通分量，4，5，6是另外一個。當我們尋找1所在的強連通分量的時候，很有可能會把4，5，6這三個點也帶進來。但問題是它們是自成分量的，并不應該算在1的強連通分量當中。

我們整理一下上面的分析和思路可以發現強連通分量分解這個算法的核心其實就是解決這兩個問題，就是完備性問題。完備意味著不能遺漏也不能冗余和錯誤，我們想明白核心問題所在之后就很容易搭建起思維框架，接下來我們再來看算法的描述會容易理解得多。

算法細節

Tarjan算法的第一個機制是時間戳，也就是在遍歷的時候對每一個遍歷到的點打上一個值。這個值表示這是第幾個遍歷的元素。

這個應該很好理解，我們只需要維護一個全局的變量，在遍歷的時候去讓它自增就可以了。我們來寫下Python代碼給大家演示一下：

stamp = 0 
stamp_dict = {}def dfs(u): 
    stamp_dict[u] = stamp    stamp += 1 
    for v in Graph[u]: 
        dfs(v) 

通過時間戳我們可以知道每個點被訪問的順序，這個順序是正向順序。舉個例子，比如說假設u和v兩個點，u的時間戳比v小。那么它們之間的關系只有兩種可能，第一種是u能夠連通到v，說明從u到v的鏈路可以走通。第二種是u不能連通到v，這種情況不論反向的從v到u能否連通都不具有討論意義，因為它們一定不能互相連通。

所以我們想要找到連通的通路還需要找到反向的路徑，在Kosaraju算法當中我們是通過反向圖來實現的。在Tarjan當中則采取了另外一種方法。因為我們已經知道各個點的時間戳了，我們完全可以通過時間戳來尋找反向的路徑。什么意思呢?其實很簡單，當我們在遍歷u的時候如果遇到了一個比u時間戳更小的v，那么說明就存在一條反向的路徑從u通向v。如果v這時候還沒有出棧，意味著v是u的上游的話，那么也就說明存在一條路徑從v通向u。這樣就說明了u和v可以互相連通。

既然找到了一對互相連通的u和v，那么我們需要把它們記錄下來。但問題是我們怎么知道記錄到什么時候為止呢?這個邊界在哪里?Tarjan算法設計了另外一個巧妙的機制解決了這個問題。

這個機制就是low機制，low[u]表示u這個點能夠連通到的所有的點的時間戳的最小值。時間戳越小說明在搜索樹當中的位置越高，也可以理解成u能夠連通到的處在搜索樹中最高的點。那么很明顯了，這個點就是u這個點所在強連通分量所在搜索樹某一棵子樹的樹根。

這里可能有一點點繞，我們再來看張圖：

圖中節點所在的序號就是遞歸遍歷的時間戳，我們可以發現對于圖上的每個點來說它們的low值都是1。很明顯1這個點在搜索樹當中是2，3，4這三個點的祖先。也就是說這一個強連通分量的遍歷是從1這個點開始的。當1這個點出棧的時候，意味著以1位樹根的子樹已經遍歷完了，所有可能存在的強連通分量也都已經找完了。

這就帶來了另外一個問題，我們假設當前點是u，我們如何知道u這個點是否是圖中1這樣的樹根呢?有沒有什么辦法可以標記出來呢?

當然是有的，這樣的點有一個特性就是它們的時間戳等于它們的low。所以我們可以用一個數組維護找到的強連通分量，當這些強連通分量能夠遍歷到的樹根出棧的時候，把數組清空。

我們把上面的邏輯整理一下就可以寫出代碼來了：

scc = [] 
stack = [] 
def tarjan(u):    dfn[u], low[u] = stamp, stamp    stamp += 1 
 stack.append(u) 
        for v in Graph[u]: 
        if not dfn[v]: 
            tarjan(v)            low[u] = min(low[u], low[v])        elif v in stack: 
         low[u] = min(low[u], dfn[v])       if dfn[u] == low[u]: 
        cur = []        # 棧中u之后的元素是一個完整的強連通分量        while True: 
            cur.append(stack[-1]) 
            stack.pop() 
            if cur[-1] == u: 
                break 
        scc.append(cur) 

最后，我們來看一下之前講過的經典例子：

首先我們從1點開始，一直深搜到6結束，當遍歷到6的時候，DFN[6]=4，low[6]=4，當6出棧時滿足條件，6獨立稱為一個強連通分量。

同理，當5退出的時候也同樣滿足條件，我們得到了第二個強連通分量。

接著我們回溯到節點3，節點3還可以遍歷到節點4，4又可以連向1。由于1點已經在棧中，所以不會繼續遞歸1點，只會更新low[4] = 1，同樣當4退出的時候又會更新3，使得low[3] = 1。

最后我們返回節點1，通過節點1遍歷到節點2。2能連通的4點已經在棧中，并且DFN[4] > DFN[2]，所以并不會更新2點。再次回到1點之后，1點沒有其他點可以連通，退出。退出的時候發現low[1] = DFN[1]，此時棧中剩下的4個元素全部都是強連通分量。

到這里，整個算法流程的介紹就算是結束了，希望大家都可以enjoy今天的內容。