1. 項(xiàng)目概述與問(wèn)題核心最近在洛谷上刷題又碰到了P4017這道經(jīng)典題目——“最大食物鏈計(jì)數(shù)”。這道題可以說(shuō)是圖論入門后從理論走向?qū)崙?zhàn)的一道絕佳練習(xí)題它把“拓?fù)渑判颉边@個(gè)聽(tīng)起來(lái)有點(diǎn)抽象的概念和一個(gè)非常具象的生物學(xué)模型食物鏈結(jié)合在了一起。很多朋友第一次做的時(shí)候可能會(huì)被“計(jì)數(shù)”和“最大”這兩個(gè)詞繞進(jìn)去或者知道要用拓?fù)渑判虻唧w怎么把計(jì)數(shù)邏輯融合進(jìn)去就卡殼了。我自己當(dāng)初也在這里琢磨了好一陣子今天就來(lái)徹底拆解一下這道題不僅講清楚怎么做更要講明白為什么這么做以及里面有哪些容易踩的坑。簡(jiǎn)單來(lái)說(shuō)題目給我們一個(gè)食物網(wǎng)每個(gè)生物是一個(gè)點(diǎn)如果生物A吃生物B就有一條從B指向A的有向邊。題目定義“食物鏈”為從最底端的生產(chǎn)者沒(méi)有任何生物吃它即入度為0開(kāi)始到最頂端的消費(fèi)者它不吃任何其他生物即出度為0結(jié)束的一條路徑。而我們的任務(wù)就是計(jì)算出這個(gè)食物網(wǎng)中所有這樣的食物鏈也就是從任意一個(gè)入度為0的點(diǎn)到任意一個(gè)出度為0的點(diǎn)的總條數(shù)。結(jié)果需要對(duì)一個(gè)很大的數(shù)80112002取模。這本質(zhì)上是一個(gè)有向無(wú)環(huán)圖DAG上的路徑計(jì)數(shù)問(wèn)題而拓?fù)渑判蛘翘幚鞤AG上這種具有先后依賴關(guān)系問(wèn)題的利器。2. 核心思路為什么拓?fù)渑判蚴钦鈩偰玫筋}你可能會(huì)想這不就是找所有從起點(diǎn)生產(chǎn)者到終點(diǎn)頂級(jí)消費(fèi)者的路徑嗎直接深度優(yōu)先搜索DFS遍歷一遍不就行了這個(gè)想法很自然但在這個(gè)場(chǎng)景下DFS會(huì)面臨兩個(gè)致命問(wèn)題2.1 DFS的困境與拓?fù)渑判虻膬?yōu)勢(shì)首先是重復(fù)計(jì)算。想象一個(gè)簡(jiǎn)單的食物網(wǎng)草生產(chǎn)者被羊和牛吃羊和牛同時(shí)被狼吃。從草到狼有兩條路徑草-羊-狼 草-牛-狼。如果你用DFS從草開(kāi)始搜索當(dāng)搜索到狼時(shí)你會(huì)記錄找到一條路徑。但是如果圖更復(fù)雜存在多個(gè)中間節(jié)點(diǎn)匯聚到同一個(gè)節(jié)點(diǎn)的情況DFS在探索不同前驅(qū)路徑時(shí)會(huì)反復(fù)訪問(wèn)這個(gè)匯聚點(diǎn)并進(jìn)行重復(fù)的路徑計(jì)算導(dǎo)致效率極低在節(jié)點(diǎn)數(shù)N達(dá)到幾千時(shí)就會(huì)超時(shí)。其次是環(huán)的檢測(cè)。題目雖然保證了輸入數(shù)據(jù)是DAG無(wú)環(huán)但我們的算法最好具備檢測(cè)環(huán)的能力或者至少能在有環(huán)輸入下優(yōu)雅失敗雖然本題不需要。純粹的DFS如果不加特殊處理如染色法在遇到環(huán)時(shí)會(huì)陷入死循環(huán)。而拓?fù)渑判蚯∏∧芡昝酪?guī)避這兩個(gè)問(wèn)題。它的核心思想是按照節(jié)點(diǎn)的依賴關(guān)系在這里體現(xiàn)為“被吃”的先后順序生成一個(gè)線性的序列。在這個(gè)序列里任意一條有向邊u-v節(jié)點(diǎn)u都排在節(jié)點(diǎn)v之前。這意味著當(dāng)我們按照拓?fù)湫蛞来翁幚砻總€(gè)節(jié)點(diǎn)時(shí)我們保證在處理當(dāng)前節(jié)點(diǎn)v時(shí)所有可能到達(dá)v的節(jié)點(diǎn)u即v的所有“食物”都已經(jīng)被處理過(guò)了。這樣我們就可以把到達(dá)u的路徑數(shù)累加到v的路徑數(shù)上從而無(wú)后效性地、遞推式地計(jì)算出到達(dá)每個(gè)節(jié)點(diǎn)的路徑總數(shù)。2.2 狀態(tài)定義與轉(zhuǎn)移方程這是解題最關(guān)鍵的一步想通了這里代碼就呼之欲出了。我們定義一個(gè)數(shù)組dp[i]表示從任意一個(gè)起點(diǎn)入度為0的生產(chǎn)者出發(fā)到達(dá)節(jié)點(diǎn)i的路徑條數(shù)。那么狀態(tài)如何轉(zhuǎn)移呢 根據(jù)拓?fù)渑判虻男再|(zhì)當(dāng)我們處理到節(jié)點(diǎn)v時(shí)它的所有前驅(qū)節(jié)點(diǎn)u即所有存在邊u-v的節(jié)點(diǎn)都已經(jīng)被處理過(guò)了dp[u]的值已經(jīng)是確定的。那么從起點(diǎn)到達(dá)v的路徑必然是先到達(dá)某個(gè)u然后再走邊u-v。因此對(duì)于每一條從u到v的邊它都給v帶來(lái)了dp[u]條新的路徑。所以狀態(tài)轉(zhuǎn)移方程非常簡(jiǎn)單dp[v] dp[v] dp[u]對(duì)于每一條從u指向v的邊初始狀態(tài)怎么設(shè)對(duì)于所有入度為0的起點(diǎn)生產(chǎn)者它們自己就是一條路徑的起點(diǎn)所以dp[起點(diǎn)] 1。最終答案是什么所有出度為0的終點(diǎn)頂級(jí)消費(fèi)者的dp[終點(diǎn)]之和就是所有完整食物鏈的條數(shù)。注意這里dp的累加是在拓?fù)渑判虻倪^(guò)程中動(dòng)態(tài)進(jìn)行的而不是等排序完再做。這是將拓?fù)渑判蜻^(guò)程與動(dòng)態(tài)規(guī)劃結(jié)合的關(guān)鍵。3. 算法實(shí)現(xiàn)細(xì)節(jié)與代碼剖析理論清晰了我們來(lái)看具體怎么實(shí)現(xiàn)。拓?fù)渑判蛴袃煞N主流寫法Kahn算法基于入度/BFS和DFS。對(duì)于這道需要?jiǎng)討B(tài)累加路徑數(shù)的題Kahn算法是更直觀、更自然的選擇因?yàn)樗旧砭褪前凑杖攵葹?的節(jié)點(diǎn)順序進(jìn)行“剝離”的這個(gè)順序完美契合我們的遞推需求。3.1 數(shù)據(jù)結(jié)構(gòu)準(zhǔn)備首先我們需要用合適的數(shù)據(jù)結(jié)構(gòu)來(lái)存這個(gè)圖。由于N節(jié)點(diǎn)數(shù)最大為5000M邊數(shù)最大為500000是一個(gè)稀疏圖使用鄰接表比鄰接矩陣更節(jié)省空間。vectorvectorint graph(n1): 鄰接表graph[u]存儲(chǔ)所有從u出發(fā)能到達(dá)的節(jié)點(diǎn)v即u吃v注意題目輸入是“吃”的關(guān)系我們建圖時(shí)要根據(jù)dp轉(zhuǎn)移的方向來(lái)決定邊的方向這一點(diǎn)后面會(huì)細(xì)說(shuō)。vectorint in_degree(n1, 0): 每個(gè)節(jié)點(diǎn)的入度。vectorint out_degree(n1, 0): 每個(gè)節(jié)點(diǎn)的出度用于最后統(tǒng)計(jì)答案。vectorint dp(n1, 0): 動(dòng)態(tài)規(guī)劃數(shù)組含義如前所述。queueint q: 用于BFS的隊(duì)列存放當(dāng)前入度為0的節(jié)點(diǎn)。3.2 一個(gè)至關(guān)重要的細(xì)節(jié)建圖方向這是第一個(gè)容易出錯(cuò)的地方。題目輸入是a b表示a吃b即能量從b流向a。而在我們的狀態(tài)轉(zhuǎn)移dp[v] dp[u]中u是前驅(qū)v是后繼dp值是從起點(diǎn)流向v的。 因此為了符合“從食物到捕食者”的能量或路徑傳遞方向我們應(yīng)該建立一條從b指向a的邊。即graph[b].push_back(a)。同時(shí)更新a的入度in_degree[a]和b的出度out_degree[b]。3.3 Kahn算法拓?fù)渑判蚺cDP融合的過(guò)程初始化讀入數(shù)據(jù)按照上述規(guī)則建圖并統(tǒng)計(jì)每個(gè)點(diǎn)的入度和出度。起點(diǎn)入隊(duì)遍歷所有節(jié)點(diǎn)將入度為0的節(jié)點(diǎn)i加入隊(duì)列q并設(shè)置dp[i] 1。拓?fù)渑判蚺cDP遞推當(dāng)隊(duì)列不為空時(shí)取出隊(duì)首節(jié)點(diǎn)u。遍歷u的所有鄰居節(jié)點(diǎn)v即u能到達(dá)的節(jié)點(diǎn)在我們的建圖里就是被u吃的生物入度減1將v的入度in_degree[v]減1模擬從圖中移除u及其出邊。DP累加關(guān)鍵步驟將u的路徑數(shù)累加到v上dp[v] (dp[v] dp[u]) % MOD。這里直接取模防止中間結(jié)果溢出。新起點(diǎn)入隊(duì)如果v的入度減為0說(shuō)明它的所有“食物”都已被處理完可以加入隊(duì)列等待處理它的“捕食者”。統(tǒng)計(jì)答案拓?fù)渑判蚪Y(jié)束后遍歷所有節(jié)點(diǎn)將出度為0的節(jié)點(diǎn)i的dp[i]累加起來(lái)并對(duì)MOD取模即為最終答案。3.4 代碼示例C風(fēng)格描述#include iostream #include vector #include queue using namespace std; const int MOD 80112002; int main() { int n, m; cin n m; vectorvectorint graph(n 1); vectorint in_degree(n 1, 0); vectorint out_degree(n 1, 0); vectorint dp(n 1, 0); queueint q; // 建圖 for (int i 0; i m; i) { int a, b; // a eats b cin a b; // 注意建邊方向從b指向a表示能量/路徑從b流向a graph[b].push_back(a); out_degree[b]; // b的出度增加 in_degree[a]; // a的入度增加 } // 初始化隊(duì)列和dp數(shù)組 for (int i 1; i n; i) { if (in_degree[i] 0) { q.push(i); dp[i] 1; // 生產(chǎn)者作為路徑起點(diǎn) } } // 拓?fù)渑判? DP while (!q.empty()) { int u q.front(); q.pop(); for (int v : graph[u]) { // 狀態(tài)轉(zhuǎn)移 dp[v] (dp[v] dp[u]) % MOD; // 入度減1相當(dāng)于移除邊u-v in_degree[v]--; if (in_degree[v] 0) { q.push(v); } } } // 統(tǒng)計(jì)答案所有出度為0的終點(diǎn) int ans 0; for (int i 1; i n; i) { if (out_degree[i] 0) { ans (ans dp[i]) % MOD; } } cout ans endl; return 0; }實(shí)操心得在寫這部分代碼時(shí)最容易混淆的就是a和b的關(guān)系以及隨之而來(lái)的入度、出度更新和建圖方向。一個(gè)很好的檢查方法是畫一個(gè)最簡(jiǎn)單的鏈A-B-CA吃BB吃C。根據(jù)題意生產(chǎn)者是C沒(méi)被吃頂級(jí)消費(fèi)者是A不吃別人。我們的dp值應(yīng)該從C流向A。如果你建成了A-B-C的圖你會(huì)發(fā)現(xiàn)入度為0的點(diǎn)是A這顯然錯(cuò)了。正確建圖C-B-A后入度為0的是Cdp從C(1)傳到B(1)再傳到A(1)邏輯就通了。4. 關(guān)鍵問(wèn)題為什么不用DFS記憶化看到路徑計(jì)數(shù)有經(jīng)驗(yàn)的同學(xué)肯定會(huì)想到DFS記憶化搜索。這確實(shí)是一種可行的方法其思路是定義dfs(u)為從節(jié)點(diǎn)u出發(fā)到任意一個(gè)終點(diǎn)的路徑數(shù)。對(duì)于終點(diǎn)dfs(終點(diǎn))1對(duì)于其他點(diǎn)dfs(u) sum(dfs(v))其中v是u的后繼節(jié)點(diǎn)。最后把每個(gè)起點(diǎn)的dfs(起點(diǎn))加起來(lái)。這種方法在理論上是正確的對(duì)于本題也能AC。但我仍然推薦KahnDP的方案原因如下思維更直接更符合問(wèn)題本質(zhì)食物鏈的能量傳遞是單向的、有明確依賴關(guān)系的。拓?fù)渑判蚰M的就是這個(gè)“依賴解決”的過(guò)程思維鏈路非常順暢。而DFS是“探索式”的需要繞一道“從后往前推”的彎。無(wú)需處理遞歸深度和棧溢出當(dāng)圖是深度很大的鏈時(shí)DFS遞歸可能導(dǎo)致棧溢出雖然通常評(píng)測(cè)機(jī)棧空間較大但這是一個(gè)隱患。Kahn算法使用隊(duì)列是迭代過(guò)程沒(méi)有這個(gè)問(wèn)題。天然檢測(cè)入度Kahn算法在初始化時(shí)就需要找入度為0的點(diǎn)這正好是我們需要的起點(diǎn)。而DFS需要額外遍歷來(lái)尋找起點(diǎn)。性能表現(xiàn)穩(wěn)定Kahn算法的時(shí)間復(fù)雜度是O(NM)且常數(shù)因子較小。DFS記憶化雖然復(fù)雜度也是O(NM)但遞歸調(diào)用有一定開(kāi)銷。當(dāng)然DFS記憶化的寫法更簡(jiǎn)潔對(duì)于熟練的同學(xué)也是不錯(cuò)的選擇。但這道題作為拓?fù)渑判虻慕?jīng)典應(yīng)用題用Kahn算法來(lái)實(shí)現(xiàn)更能加深對(duì)算法本身的理解。5. 邊界情況與調(diào)試技巧即使思路正確實(shí)現(xiàn)時(shí)也可能被一些邊界情況卡住。下面是我在調(diào)試和幫別人排查問(wèn)題時(shí)總結(jié)的幾個(gè)常見(jiàn)坑點(diǎn)5.1 取模的時(shí)機(jī)題目要求結(jié)果對(duì)80112002取模。你是在最后累加答案時(shí)取模還是在每一步dp[v] dp[u]時(shí)取模強(qiáng)烈建議在每次加法后立即取模。因?yàn)槁窂綌?shù)可能增長(zhǎng)得非?？熘虚g結(jié)果dp[v]有可能在還沒(méi)成為最終答案前就溢出了。雖然C的int在大部分環(huán)境下是32位但安全起見(jiàn)養(yǎng)成在每次可能溢出的運(yùn)算后取模的習(xí)慣。5.2 出度的統(tǒng)計(jì)答案需要累加所有出度為0的節(jié)點(diǎn)的dp值。出度需要在建圖時(shí)同步統(tǒng)計(jì)。這里有個(gè)小技巧我們建的是從“食物”指向“捕食者”的邊(b-a)。那么對(duì)于這條邊b的出度增加了1。這個(gè)out_degree數(shù)組在拓?fù)渑判蜻^(guò)程中不會(huì)被修改只在最后統(tǒng)計(jì)時(shí)使用。務(wù)必確保統(tǒng)計(jì)的是出度為0的點(diǎn)而不是入度為0的點(diǎn)那是起點(diǎn)。5.3 大輸入量的處理N5000, M500000這是一個(gè)邊數(shù)很多的圖。使用cin/cout可能會(huì)導(dǎo)致輸入輸出超時(shí)。一個(gè)簡(jiǎn)單的優(yōu)化是關(guān)閉流同步或者使用scanf/printf。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);5.4 環(huán)的潛在風(fēng)險(xiǎn)雖然本題保證無(wú)環(huán)一個(gè)健壯的拓?fù)渑判驅(qū)崿F(xiàn)應(yīng)該能檢測(cè)到環(huán)。在Kahn算法中如果算法結(jié)束后還有節(jié)點(diǎn)的入度不為0即沒(méi)有全部加入過(guò)隊(duì)列那么就說(shuō)明圖中存在環(huán)。本題雖然保證了無(wú)環(huán)但在實(shí)際競(jìng)賽或工程中加上這個(gè)檢測(cè)能讓你更快地發(fā)現(xiàn)輸入數(shù)據(jù)的錯(cuò)誤。// 拓?fù)渑判蚪Y(jié)束后檢查 bool hasCycle false; for(int i 1; i n; i) { if(in_degree[i] 0) { hasCycle true; break; } } if(hasCycle) { // 處理有環(huán)情況本題可忽略 }6. 算法復(fù)雜度與優(yōu)化空間分析時(shí)間復(fù)雜度主要消耗在兩部分。一是讀入數(shù)據(jù)和建圖O(M)。二是Kahn算法的過(guò)程每個(gè)節(jié)點(diǎn)和每條邊都被訪問(wèn)一次也是O(NM)。因此總時(shí)間復(fù)雜度為 O(NM)對(duì)于最大數(shù)據(jù)規(guī)模是完全可以接受的?？臻g復(fù)雜度鄰接表存儲(chǔ)圖需要 O(NM)in_degree,out_degree,dp數(shù)組各需要 O(N)隊(duì)列在最壞情況下需要 O(N)。總空間復(fù)雜度為 O(NM)。優(yōu)化方向?qū)τ谶@道題上述解法已經(jīng)是最優(yōu)解之一。但我們可以思考一些變種或擴(kuò)展如果需要輸出所有路徑那么上述DP方法就不行了必須使用DFS回溯。復(fù)雜度會(huì)指數(shù)級(jí)增長(zhǎng)僅適用于非常小的圖。如果圖非常稠密M接近N^2鄰接表依然優(yōu)于鄰接矩陣但隊(duì)列操作和遍歷邊的開(kāi)銷會(huì)變大。不過(guò)本題M上限50萬(wàn)對(duì)于N5000來(lái)說(shuō)遠(yuǎn)未達(dá)到稠密程度。并行計(jì)算理論上拓?fù)渑判虻哪承╇A段可以并行處理入度為0的節(jié)點(diǎn)但對(duì)于算法競(jìng)賽和此題規(guī)模無(wú)需考慮。7. 舉一反三拓?fù)渑判蜻€能解決什么問(wèn)題通過(guò)P4017這道題我們掌握了拓?fù)渑判蚪鉀QDAG上路徑計(jì)數(shù)問(wèn)題的核心套路定義狀態(tài)到達(dá)某點(diǎn)的方案數(shù)利用拓?fù)湫虮ＷC無(wú)后效性進(jìn)行遞推。這個(gè)套路可以遷移到許多類似場(chǎng)景項(xiàng)目安排/課程學(xué)習(xí)順序有前置依賴的任務(wù)求完成所有任務(wù)的總方案數(shù)假設(shè)某些任務(wù)可以并行。dp[i]可以表示完成前i個(gè)任務(wù)按某種拓?fù)湫虻姆桨笖?shù)或者表示到達(dá)任務(wù)i的狀態(tài)數(shù)。關(guān)鍵路徑計(jì)算在AOE網(wǎng)邊表示活動(dòng)中求從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑工期以及哪些活動(dòng)是關(guān)鍵的。這需要計(jì)算最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間其計(jì)算過(guò)程就是正反兩次拓?fù)渑判?。編譯順序確定大型項(xiàng)目中源文件之間有依賴關(guān)系編譯器需要確定一個(gè)編譯順序確保每個(gè)文件被編譯時(shí)其依賴都已編譯好。這就是拓?fù)渑判虻慕?jīng)典應(yīng)用。解決循環(huán)依賴在軟件包管理如apt, yum或構(gòu)建工具如Make, Gradle中檢測(cè)并解決循環(huán)依賴問(wèn)題。理解了這個(gè)模式以后再看到“有向無(wú)環(huán)圖”、“依賴關(guān)系”、“順序”、“計(jì)數(shù)”這些關(guān)鍵詞時(shí)拓?fù)渑判蚓蛻?yīng)該成為你工具箱里的首選工具之一了。最后再分享一個(gè)調(diào)試小技巧對(duì)于圖論問(wèn)題當(dāng)你的代碼結(jié)果不對(duì)時(shí)不要只看大數(shù)據(jù)。自己構(gòu)造幾個(gè)極小規(guī)模的測(cè)試用例比如3個(gè)節(jié)點(diǎn)2條邊然后手工模擬你的算法過(guò)程一步一步對(duì)照中間變量in_degree,dp, 隊(duì)列內(nèi)容很快就能定位到是思路問(wèn)題還是代碼實(shí)現(xiàn)問(wèn)題。對(duì)于P4017一定要用那個(gè)“誰(shuí)吃誰(shuí)”的簡(jiǎn)單鏈來(lái)驗(yàn)證你的建圖方向這是最快最有效的檢查方法。