有向圖里的“互相可達(dá)”現(xiàn)象其實比你想的更常見。模塊A調(diào)用模塊B模塊B又回調(diào)模塊A兩個微服務(wù)互為依賴社交平臺上你關(guān)注我、我關(guān)注你這些一旦被畫成一張有向圖就會出現(xiàn)一群節(jié)點互相之間都能走通的小團(tuán)體。這群小團(tuán)體在圖論里有個正式名字強(qiáng)連通分量縮寫就是SCC。為什么要揪出SCC因為只要找到它很多棘手問題會瞬間變簡單循環(huán)依賴一眼就能看出來一團(tuán)互相糾纏的邏輯可以當(dāng)成一個整體處理原本帶環(huán)的圖還能被壓成沒有環(huán)的DAG。Tarjan算法則是求SCC最常見的高效解法它用一次DFS就能把所有SCC找完代碼短、常數(shù)小是搞算法、搞工程、準(zhǔn)備競賽的人都繞不開的基礎(chǔ)功。這篇文章我會把Tarjan從概念、原理、代碼到避坑點完整梳理一遍就算你之前只看過一點DFS跟著推一遍也能徹底搞懂。1. 從一道圖的“互相可達(dá)”說起強(qiáng)連通分量到底找什么1.1 什么是SCC一個極大“互達(dá)圈”的精確定義在有向圖里如果從u能走到v并且從v也能走到u就說u和v強(qiáng)連通。注意這是有向圖專屬的概念無向圖只要連通就行但“有向”意味著路徑方向不能隨便反向。一個強(qiáng)連通分量就是滿足“內(nèi)部任意兩點互相可達(dá)”的極大節(jié)點集合。重點在這個“極大”不是隨便找?guī)讉€互相可達(dá)的點就能叫分量而是必須把所有能互相到達(dá)的節(jié)點都裝進(jìn)來。舉個很容易懂的比方。假設(shè)有一場線下活動參與者之間可以“單向認(rèn)識”別人。你認(rèn)識小明小明也認(rèn)識你那你們倆就形成了一個小圈子。如果小紅能通過小明認(rèn)識你、你也通過小紅認(rèn)識她那她也要被拉進(jìn)這個圈子只要有人能被圈子里的某條單向鏈拉進(jìn)來并且也能通過另一條單向鏈回到圈子里的任意人那就必須吸收進(jìn)來直到再也塞不進(jìn)新人。這個最終收滿的圈子才是SCC。從代碼角度看判斷“任意兩點互相可達(dá)”最粗暴的方法是Floyd-Warshall或者對每個點跑BFS復(fù)雜度高得離譜。Tarjan能在一次DFS里把這些極大圈子干凈利落地切出來這個能力就是它最大的價值。后面你會看到Tarjan不是靠定義去“檢查”可達(dá)性而是靠DFS的遍歷順序和回邊識別來自動切分思路完全不一樣。1.2 SCC能解決的真實問題循環(huán)依賴、社區(qū)、2-SATSCC不是純粹的理論玩具它在真實工程里的應(yīng)用非常多。我做過的項目里遇到最典型的場景就是依賴關(guān)系檢測模塊A import BB import A這種循環(huán)依賴編譯期會報錯但運行時發(fā)現(xiàn)的循環(huán)調(diào)用往往藏得很深。把整個調(diào)用關(guān)系建成一張有向圖跑一次SCC所有成環(huán)的模塊自動歸為一組一眼就能看出是誰在抱團(tuán)。數(shù)據(jù)庫和微服務(wù)領(lǐng)域也有類似的場景。多個服務(wù)互相調(diào)用來調(diào)用去一旦其中一個掛了調(diào)用鏈可能會形成死鎖或者雪崩。用SCC把這些“互相咬合”的服務(wù)組識別出來就可以在發(fā)布順序、熔斷策略、超時設(shè)置上做專門處理。比如兩個服務(wù)A和B互相依賴那么發(fā)布時就不能先停A再停B必須當(dāng)成一個整體去規(guī)劃否則中間任何一個時刻請求都可能打到半個不可用的系統(tǒng)上。競賽算法里SCC更是一塊跳板求完強(qiáng)連通分量后可以把每個分量縮成一個點整張圖變成DAG拓?fù)渑判?、動態(tài)規(guī)劃、最長鏈問題都能接踵而至。我后面會講的2-SAT直接把每個布爾變量的真假拆成兩個節(jié)點再通過SCC判斷是否矛盾套路一套一個準(zhǔn)。還有社交網(wǎng)絡(luò)里的“朋友圈”挖掘本質(zhì)上也是找出互相關(guān)注得最緊密的一坨人?？傊甋CC是圖論中最通用的“聚類工具”之一。1.3 為什么優(yōu)先學(xué)Tarjan一次DFS就把活干完求SCC的算法不止一個常見的有Kosaraju、Tarjan和Gabow。Kosaraju思路簡單先在第一張圖上跑DFS記錄拓?fù)漤樞蛟僭诜较蛳喾吹膱D上按逆序跑一遍DFS輸出結(jié)果。它正確性容易理解但需要兩次DFS還要能快速訪問原圖的反向圖。你要是用鄰接表存圖就得額外建一個逆圖內(nèi)存和時間都會多一份開銷。Tarjan走的是另一條路只做一次DFS邊搜邊維護(hù)節(jié)點的時間戳和回溯值用一個棧把尚未歸屬的節(jié)點串起來。它不需要逆圖常數(shù)也小寫完就是幾十行。代價是第一次看會有點繞dfn、low、棧三者互相配合不像Kosaraju那么直觀。所以我一般給身邊人建議先學(xué)Kosaraju找感覺再啃Tarjan拿效率如果直接就想在競賽或者工程里高效落地Tarjan更值得下功夫。2. Tarjan算法的核心原理一套可以手推的直覺2.1 dfn和low到底記錄了什么Tarjan依賴兩個核心標(biāo)記dfn和low。dfn是“深度優(yōu)先搜索編號”也可以理解成上門服務(wù)的時間戳每個節(jié)點在被DFS第一次訪問時按順序編號你進(jìn)了這間房就在門上刻一個遞增的數(shù)字。low是“通過當(dāng)前DFS子樹走到的最早回退編號”當(dāng)你在房間里探索各種邊時如果發(fā)現(xiàn)某條邊能繞回到編號更小的房間就把low更新成那個更小的編號。聽起來抽象但換一個思維模型就順了。想象你在一個迷宮里探路每進(jìn)入一個新房間就給它發(fā)一個遞增的門牌號這就是dfn。迷宮里有單向密道你站在當(dāng)前房間順著密道看能不能回到某個已經(jīng)發(fā)過牌子、人還沒走完的舊房間。能回到的最早那個門牌號就是low要記錄的東西。等某個房間的low等于自己的dfn就說明從這里往后所有人只能在自己管轄的迷宮里折騰通不出去可以關(guān)門把這一批人打包了。一個關(guān)鍵細(xì)節(jié)判斷能不能用舊房間更新low時不能光看“這個點被訪問過”還要看它是不是還在當(dāng)前處理棧里。如果某個舊房間已經(jīng)被完整處理好并彈出說明它屬于一個已經(jīng)成團(tuán)的分量跟當(dāng)前分支已經(jīng)沒有關(guān)系了再用它更新low會把相鄰分量錯誤合并。2.2 標(biāo)準(zhǔn)流程從入棧到彈棧的完整框架Tarjan的遞歸代碼結(jié)構(gòu)本質(zhì)上是對DFS做了一些附加操作。我先把流程鋪開對每個尚未訪問的節(jié)點調(diào)用一次tarjan函數(shù)函數(shù)內(nèi)部先給當(dāng)前節(jié)點u分配dfn和low然后入棧接著依次查看u的每個鄰居v。如果v沒訪問過就遞歸處理它處理完回來用low[v]更新low[u]如果v訪問過并且還在棧里就用dfn[v]更新low[u]如果v已經(jīng)出棧直接忽略。等所有鄰居處理完檢查low[u]是否等于dfn[u]如果相等就不斷彈棧直到把u彈出這些彈出來的節(jié)點一起構(gòu)成一個SCC。整個框架里棧的作用極其關(guān)鍵。它專門存放“已經(jīng)被訪問、但還沒被歸類到某個SCC”的節(jié)點。為什么需要它因為DFS在回溯時會遇到一系列處于“半完成”狀態(tài)的節(jié)點這些節(jié)點之間可能通過回邊組成環(huán)但它們還沒到結(jié)算時刻。棧把這些候選節(jié)點按訪問時間壓在一起一旦某個根節(jié)點條件滿足從它往上直到棧頂?shù)墓?jié)點都能被一起彈出。這里有初學(xué)者常常忽略的地方遞歸處理完子樹后用low[v]更新low[u]只是其中一條更新路徑判斷“v訪問過且在棧中”時的更新同樣必不可少。如果漏掉這種情況下用dfn[v]更新等于無視了從u直接指向祖先的回邊很多環(huán)根本識別不出來。你可以在示例圖里故意去掉這句會發(fā)現(xiàn)問題非常隱蔽。2.3 為什么 low[u] dfn[u] 就是根節(jié)點這是整個算法最值得想明白的地方。一個節(jié)點u被訪問后它的low值表示在它自己的DFS子樹內(nèi)通過各種邊能追溯到的、還在棧中的最小編號。如果這個最小值比u自己的dfn還小說明u這個分支里一定有回邊通到了DFS樹里更早的祖先那u和那個祖先處在同一個強(qiáng)連通分量中此刻不能把u切出去。反過來當(dāng)u的所有鄰居都處理完low[u]依然等于dfn[u]意思就是不管怎么繞u的子樹的回邊最遠(yuǎn)也就到u本身通不到u的任何祖先。那么當(dāng)前棧中從u到棧頂?shù)乃泄?jié)點就構(gòu)成了一個封閉的“互達(dá)團(tuán)體”。為什么是封閉的因為如果他們中間有指向更早節(jié)點的回邊這個更早的編號一定小于dfn[u]low[u]就會被更新既然沒有被更新說明往外走的路都被切斷了。此時把棧頂?shù)絬的一串節(jié)點彈出就是一個SCC而且因為它是在DFS過程中按遞歸邊界劃分出來的天然是極大的。這個洞察能幫你省掉很多死記硬背。每次看到low[u] dfn[u]腦子里的第一反應(yīng)應(yīng)該是門牌號最小的一間房被關(guān)上了整個房間組成了一個獨立區(qū)域。2.4 復(fù)雜度為什么只有O(VE)以及更新細(xì)節(jié)的講究Tarjan之所以高效是因為每個節(jié)點最多入棧出棧一次每條邊最多被檢查一次。總的DFS遍歷是O(VE)棧操作是O(V)合起來還是O(VE)?？臻g上需要dfn、low、scc三個數(shù)組和一個棧都是O(V)級別。這個量級意味著它在百萬節(jié)點級別的圖上也完全扛得住只要注意遞歸深度問題。有個很多模板會寫但不一定解釋清楚的點當(dāng)鄰居v已經(jīng)訪問過并且在棧中時標(biāo)準(zhǔn)更新是low[u] min(low[u], dfn[v])而不是low[v]。理由是這樣v在棧中意味著v是當(dāng)前DFS路徑上的祖先dfn[v]是能夠準(zhǔn)確度量這個祖先層次的編號。用dfn[v]更新語義最干凈——一條回邊指回編號dfn[v]的節(jié)點我就能把low縮小到dfn[v]。有些實現(xiàn)用low[v]替換也常常能跑對因為祖先的low可能本身就更小但為了和論文原版保持一致、也為了推導(dǎo)時不產(chǎn)生歧義建議始終寫dfn[v]。如果你看別的博客能看到low[v]的寫法不必立刻覺得別人錯了但和標(biāo)準(zhǔn)版對比時要有意識兩種寫法都把“回到棧中最早祖先”這條信息傳給了u差別只在取的是祖先的dfn還是祖先的low。對絕大多數(shù)數(shù)據(jù)這兩者結(jié)果一致但標(biāo)準(zhǔn)寫法更能反映算法本意。3. 代碼實現(xiàn)與手工模擬從模板到徹底跑通3.1 一份帶注釋的C模板我直接給出一個能在競賽和工程里改著用的模板基于鄰接表。const int MAXN 100005; vectorint G[MAXN]; int dfn[MAXN], low[MAXN], sccId[MAXN]; int timer 0, sccCnt 0; stackint st; bool inStack[MAXN]; void tarjan(int u) { dfn[u] low[u] timer; st.push(u); inStack[u] true; for (int v : G[u]) { if (!dfn[v]) { // v 還沒被訪問過 tarjan(v); low[u] min(low[u], low[v]); // 用子樹結(jié)果更新 } else if (inStack[v]) { // v 訪問過且還在棧中說明是祖先 low[u] min(low[u], dfn[v]); // 用祖先的 dfn 更新 } // 如果 v 已經(jīng)出棧說明屬于別的 SCC忽略 } if (low[u] dfn[u]) { sccCnt; while (true) { int x st.top(); st.pop(); inStack[x] false; sccId[x] sccCnt; if (x u) break; } } } // main 里 for (int i 1; i n; i) { if (!dfn[i]) tarjan(i); }這段代碼有幾個位置值得停下來多看兩眼。第一個是dfn[u] low[u] timer必須放在函數(shù)最前面保證每個節(jié)點只有一次被分配編號第二個是遍歷鄰居時的三種分支順序不能亂第三個是彈棧時先彈出節(jié)點再標(biāo)記sccId和inStackfalse最后判斷是否到u這個循環(huán)把從棧頂?shù)絬的所有節(jié)點一次性歸到一個分量里。漏掉其中任何一步都會造成分量殘缺或者重復(fù)入棧。有個小建議實際寫的時候可以把vectorint G[MAXN]換成vectorvectorint G或者鄰接表封裝都沒問題。關(guān)鍵是把dfn、low、inStack的理解帶出去換語言只是換個殼。用Python寫的話邏輯完全一致只要把數(shù)組換成list、遞歸前設(shè)置好遞歸深度上限就行。3.2 手工模擬一個簡單圖讓過程“肉眼可見”紙上談兵一千遍不如手動跑一遍。我拿一張六條邊的圖0→1、1→2、2→0、2→3、3→4、4→3。這個圖應(yīng)該有兩個強(qiáng)連通分量{0,1,2}是一個三節(jié)點環(huán){3,4}是一個兩節(jié)點環(huán)。從0開始DFS。進(jìn)入0dfn[0]1low[0]1入棧。走到1dfn[1]2low[1]2入棧。走到2dfn[2]3low[2]3入棧。2的鄰接邊有兩條第一條去0發(fā)現(xiàn)0還在棧中于是low[2]min(3,1)1第二條去33沒訪問過遞歸進(jìn)入3dfn[3]4low[3]4入棧。3走進(jìn)4dfn[4]5low[4]5入棧。4發(fā)現(xiàn)可以去3而且3在棧中于是low[4]min(5,4)4。4處理完回到33用low[4]更新自己low[3]min(4,4)4。此時low[3]dfn[3]4命中根節(jié)點彈棧直到3先彈4再彈3SCC編號1分給{3,4}。接著回溯到22因為已經(jīng)訪問完3這個分支用low[3]4更新low[2]但min(1,4)還是1。2處理完low[2]1不等于dfn[2]3不彈?；氐?low[1]min(2,1)1不彈?；氐?low[0]min(1,1)1low[0]dfn[0]1命中彈棧直到0先彈2、再彈1、最后彈0SCC編號2分給{0,1,2}。這個例子把兩種更新都覆蓋了一條回邊直接指向棧中祖先用dfn更新low一條樹邊通過子樹遞歸用low[v]更新low。彈棧發(fā)生在low等于dfn的節(jié)點上且每次都把一批節(jié)點整體帶走。拿一張紙照著這個流程寫一遍比看十遍代碼都管用。你也可以自己隨便畫一張帶環(huán)的圖然后按這個節(jié)奏手推很快就建立起對算法時序的直覺。3.3 大圖怎么辦非遞歸寫法才是穩(wěn)妥方案如果圖的節(jié)點數(shù)到幾十萬、上百萬遞歸調(diào)用很容易把系統(tǒng)棧壓爆。C在Windows下可以加#pragma comment(linker, /STACK:102400000,102400000)Linux下可以調(diào)ulimit -s unlimited但這只是臨時手段。更穩(wěn)定的做法是把Tarjan改成非遞歸手動用棧模擬系統(tǒng)調(diào)用棧。思路是把每個節(jié)點包裝成一個“任務(wù)幀”記錄當(dāng)前節(jié)點u、當(dāng)前遍歷到鄰接表第幾個鄰居、以及u作為遞歸返回點的狀態(tài)。進(jìn)棧時先做dfn賦值和入算法棧每處理完一個鄰居根據(jù)情況更新low等所有鄰居處理完再判斷l(xiāng)owdfn并完成彈棧。代碼會比遞歸版長一些但復(fù)雜度不變而且能處理超大圖。如果只是在學(xué)校作業(yè)或中小型數(shù)據(jù)集上用遞歸版完全夠。但一旦面對百萬節(jié)點的真實業(yè)務(wù)圖非遞歸就是剛需。我自己的習(xí)慣是小圖調(diào)試用遞歸版邏輯清楚正式處理大圖時寫一版非遞歸常備在模板庫里。如果你只是學(xué)習(xí)算法先把遞歸版看懂非遞歸更多是工程上的“保險橋”。4. 易錯點、常見坑和驗證技巧4.1 我踩過的四個經(jīng)典錯誤第一把更新目標(biāo)寫錯寫成dfn[u] min(dfn[u], dfn[v])。這讓dfn這個“唯一時間戳”被反復(fù)修改整個算法的編號體系直接崩潰low和dfn的關(guān)系徹底亂套。每次寫完代碼用肉眼掃一遍low[u] min(...)確認(rèn)左邊是low不是dfn。第二彈棧循環(huán)寫成只彈一次或者while (st.top() ! u)但忘記先處理棧頂。正確順序是先拿到棧頂節(jié)點、彈出、標(biāo)記inStack和sccId、再判斷是不是u。有人習(xí)慣先判等再彈最后會漏掉u本身。第三只從一個節(jié)點開始跑算法。主函數(shù)里如果不是for (int i1; in; i) if (!dfn[i]) tarjan(i);那么第一棵DFS樹之外的孤立點和分支就會被漏掉。很多新手用一個單連通圖測沒問題換多分量圖就出奇怪結(jié)果十有八九是這個原因。第四忘記在彈棧時清除inStack[x]。這個標(biāo)記很關(guān)鍵如果不清后續(xù)節(jié)點看到它還在棧里會用它的dfn更新low把已經(jīng)結(jié)束的SCC錯誤牽扯回來。調(diào)試時一旦發(fā)現(xiàn)SCC的節(jié)點編號混亂先檢查inStack的清理邏輯。4.2 如何驗證你的SCC代碼是對的最穩(wěn)妥的驗證方法是對拍寫一個暴力解法用BFS或Floyd判斷任意兩點是否互相可達(dá)然后合并出所有極大強(qiáng)連通塊再和Tarjan的輸出對比。暴力正確性一目了然雖然慢只在小圖上跑就行。隨機(jī)生成幾十張小圖兩邊結(jié)果一致代碼基本就穩(wěn)了。再準(zhǔn)備一組邊界測試空圖、單點圖、自環(huán)圖、一條鏈、一個完整有向環(huán)、兩個互不相交的環(huán)、帶孤立點的圖、完全有向圖。特別是自環(huán)很多人會混淆單個帶自環(huán)的節(jié)點本身就是一個SCC完全有向圖中所有節(jié)點屬于同一個SCC。把這些case跑一遍很多隱患能提前暴露。另外可以檢查輸出分量的性質(zhì)分量內(nèi)任意兩點互相可達(dá)分量之間壓縮后不存在環(huán)。如果發(fā)現(xiàn)縮點后有環(huán)那說明某個強(qiáng)連通塊被切碎了。這個性質(zhì)檢查寫起來也不難遍歷每條邊u→v如果sccId[u] ! sccId[v]就在縮點圖上加一條邊最后對這個縮點圖再排一遍拓?fù)浠驒z查環(huán)。4.3 Tarjan和Kosaraju怎么選對比維度TarjanKosaraju圖的遍歷次數(shù)1次2次是否依賴逆圖否是空間開銷O(V)棧需要原圖和逆圖理解門檻中等偏高低邏輯直觀適用場景工程、競賽、大圖教學(xué)入門、實現(xiàn)簡單優(yōu)先我的實際建議分兩層如果是學(xué)習(xí)階段先寫Kosaraju它幾乎不會寫錯能幫你形成“SCC就是閉包”的正確直覺如果是要處理競賽題或者上生產(chǎn)Tarjan才是更省心省內(nèi)存的選擇。兩者結(jié)果完全一致所以你甚至可以先用Kosaraju交叉驗證Tarjan的正確性。5. 把SCC用起來縮點、2-SAT與更多場景5.1 縮點變成DAG后續(xù)處理的全新展開把每個SCC壓縮成一個點邊由原圖關(guān)系繼承就得到一張有向無環(huán)圖。為什么無環(huán)因為如果壓縮后還有環(huán)環(huán)上所有縮點對應(yīng)的原始節(jié)點集合其實可以合并成更大的強(qiáng)連通分量這就違背了“極大”的定義。有了DAG很多問題都能放心做拓?fù)渑判?、最長路DP、關(guān)鍵路徑、依賴分層。舉個例子處理一組帶約束的構(gòu)建任務(wù)時互相依賴的任務(wù)構(gòu)成強(qiáng)連通塊壓縮后每個塊要么先執(zhí)行要么后執(zhí)行不會陷入循環(huán)等待。配合拓?fù)渑判蚓湍芙o出一個無環(huán)的執(zhí)行順序。工程里的“依賴圖分析器”基本就是這個邏輯。做競賽題時縮點也經(jīng)常是第一步先縮點然后在DAG上跑動態(tài)規(guī)劃復(fù)雜度從原來的NP問題降成多項式問題。5.2 用SCC解2-SAT一個經(jīng)典套路2-SAT是判斷一組布爾約束能否同時滿足的問題。它的核心技巧是把每個變量x拆成兩個節(jié)點x為真和x為假。每條約束(a∨b)轉(zhuǎn)成兩個蘊(yùn)含邊(?a→b)和(?b→a)意思是如果a不成立b必須成立如果b不成立a必須成立。建完圖后跑SCC如果x和?x落在同一個強(qiáng)連通分量里說明自相矛盾無解否則一定有可行賦值按SCC的拓?fù)淠嫘蚪o每個變量賦值即可。這套東西在博弈題、調(diào)度題、邏輯判斷題里出現(xiàn)頻率很高。很多看起來毫無關(guān)系的條件判定最后都能被拆成一堆蘊(yùn)含邊扔進(jìn)SCC里。理解了SCC等于拿到了2-SAT的鑰匙。你可能不會天天寫2-SAT但一旦遇到Tarjan就是那個隱藏在背后的基礎(chǔ)工具。5.3 其他場景從編譯器到社交網(wǎng)絡(luò)我前面提到的循環(huán)依賴檢測、微服務(wù)調(diào)用分組、社交圈子挖掘都只是冰山一角。在編譯器中函數(shù)調(diào)用的遞歸環(huán)可以通過SCC識別在靜態(tài)分析中數(shù)據(jù)流的循環(huán)結(jié)構(gòu)可以用SCC化簡在推薦系統(tǒng)里強(qiáng)連通簇常常意味著緊密的關(guān)系群可以直接拿來當(dāng)特征。再往后學(xué)Tarjan的思路還被推廣到割點、橋、雙連通分量它們和SCC共用同一套“dfn low”的思維框架學(xué)會了Tarjan等于打開了圖連通性分析的整扇門。最后說點我自己的實踐體會。Tarjan這套思路看起來繞但你一旦親手推演一遍會發(fā)現(xiàn)它其實就是“時間戳棧區(qū)間閉合”的組合拳。我當(dāng)初第一次接觸時也是卡在“為什么彈棧到u就是分量”上很久后來我把代碼里的遞歸調(diào)用全部展開成手寫棧之后突然就想通了。如果你也卡在某個環(huán)節(jié)強(qiáng)烈建議把示例圖換成自己隨便畫的一張逼著自己一步步寫出dfn、low和棧的狀態(tài)這個過程的收獲遠(yuǎn)大于反復(fù)背模板。以后遇到任何跟“互相可達(dá)”“閉環(huán)分組”沾邊的問題先想到跑一遍SCC很多難題的最優(yōu)解就藏在這幾十行代碼里。