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