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