為任務排序：拓樸排序是什麼
想像一張有向圖，它的邊代表「必須先於」。有先修需求的課程、依賴前面產出的建置步驟、引用前面章節的後面章節——只要 u 必須發生在 v 之前，就畫一條 u 到 v 的邊。一個拓樸順序是把所有頂點排成一列，使得每條邊都指向前方：對每條邊 u 到 v，u 出現在 v 的左邊某處。把頂點按這個順序由左到右排好，就沒有任何箭頭會往回指。若這樣的排列存在，你就能照這個順序一次做一項任務，永遠不違反任何依賴。這就是有向無環圖的拓樸排序，也是圖探索帶給我們最乾淨的成果之一。
先說兩個誠實的提醒。第一，拓樸順序存在若且唯若這張圖沒有有向環。一個環 a 到 b 再到 a，是一個同時主張「a 在 b 前」與「b 在 a 前」的依賴——沒有任何排列能同時滿足兩者，所以根本無從排起。這正是為什麼輸入必須是 DAG（有向無環圖）。第二，這個順序通常不唯一：若兩項任務之間沒有任何路徑，誰先誰後都行，所以一張圖可以有許多個有效的拓樸順序。演算法產出其中之一，而非某個唯一「正確」的。
完成時間替你做了工
這裡有上一篇指南鋪好的驚喜。當深度優先搜尋探索一個頂點時，它蓋下兩個時間戳：第一次抵達時的發現時間，以及把底下所有可達之處都探索完、正要退出時的完成時間。這個論斷近乎神奇：在一張 DAG 裡，若你把頂點按完成時間遞減排序，就得到一個有效的拓樸順序。等價地說，只要每個頂點一完成就把它推進一個堆疊；把堆疊彈出，就照拓樸順序把頂點交給你。不必額外掃一遍、不必用另一把鍵排序——完成順序反過來，就已經是答案。
為什麼成立？取任一條邊 u 到 v，看看深度優先搜尋對它必然會怎麼處理。我們要證明 u 比 v 晚完成，這樣在「完成時間反向」的排列裡 u 才會落在 v 左邊。檢視邊 u 到 v 的那一刻，恰好只有兩種情形。若 v 尚未被發現，DFS 會從 u 潛入 v，並在回頭去完成 u 之前先完成 v——所以 v 先完成，沒問題。若 v 已經完成，那它在我們連 u 都還沒檢視完之前就完成了，所以 u 仍然較晚完成，也沒問題。剩下唯一的可能——v 已被發現但尚未完成——會代表 v 是一個還在遞迴堆疊上的祖先，使得 u 到 v 成為一條回邊，洩漏出一個環。而在 DAG 裡沒有回邊，所以那種情形永不發生。於是每條邊都從一個較晚完成的頂點指向一個較早完成的頂點，這在反向順序裡恰好就是指向前方。
為什麼一個拓樸順序值得擁有
拓樸順序不只是一張整齊的清單；它是一張許可證，讓你能以「每個依賴都已完成」的順序處理頂點。最乾淨的回報是 DAG 上的最短路徑。在一般圖上，單源最短路徑需要戴克斯特拉或貝爾曼-福特，但若圖是無環的，你可以做一件更簡單、更快的事：把頂點按拓樸順序排好，並依此順序鬆弛每個頂點的出邊。因為一個頂點的所有前驅都排在它前面，當你抵達某頂點時，它的最佳距離早已定案。這在純 O(V + E) 時間內完成，而且不像戴克斯特拉，它毫無怨言地處理負邊權——讓它正確的是無環性，而非權重的正負號。
同樣的「依依賴順序處理」想法，正是讓 DAG 上的動態規劃合法的原因。任何動態規劃私底下都是一張圖：子問題是頂點，從子問題 a 到子問題 b 的一條邊代表 b 的答案需要 a 的答案。一個有效的求值順序，恰恰就是那張子問題圖的一個拓樸順序，而這個動態規劃有良好定義的答案，若且唯若依賴圖是無環的。所以拓樸排序並非一個冷門的圖技巧——它正是你在本階梯前面遇到的那些求值順序之所以被允許存在的結構性原因。
強連通分量：能彼此到達的群落
拓樸順序假設了沒有環。強連通分量則正面迎向環。在一張有向圖裡，若 u 到 v 有路徑、且 v 回到 u 也有路徑，就稱兩個頂點 u 與 v 互相可達。一個強連通分量（SCC）是一組極大的頂點集合，其中任兩個頂點都互相可達——一個你能從任何人走到任何人、再走回來的群落。一個沒有環穿過它的單一頂點，自成一個大小為一的 SCC。較大的 SCC 恰恰就是那些有向環，在重疊處被熔接在一起。
美妙之處在這裡。把每個 SCC 縮成單一個超級頂點，並在兩個超級頂點之間畫一條邊——只要有任何邊跨越它們所屬分量。結果——這張縮圖——永遠是無環的。它非如此不可：若縮圖有環，那條環上的所有 SCC 都會互相可達，本來就該合併成一個更大的 SCC，與極大性矛盾。所以每張有向圖都可拆成若干 SCC，其縮圖是一張 DAG，這代表你可以對縮圖跑拓樸排序。SCC 與拓樸順序是同一套工具：SCC 找出環，接著縮圖遞給你一張可排序的 DAG。
找出 SCC：兩趟深度優先搜尋
最好教的 SCC 方法，科薩拉朱演算法，重複使用了上面的一切，只多加一樣新材料：反向圖，也就是把每條邊翻轉後的同一張圖。反向圖有著完全相同的 SCC（互相可達不在乎你把箭頭標成哪個方向），但翻轉邊會打亂哪些分量能到達哪些分量——而這個打亂，正是讓第二趟 DFS 能一次一個地把各分量剝離出來的關鍵。
- 對整張圖跑一趟 DFS，並在每個頂點的完成時間把它推進一個堆疊——正是先前那個拓樸順序的技巧，即便圖現在可能有環。
- 把每條邊翻轉，建出反向圖。
- 按順序把頂點從堆疊彈出；對每個尚未被歸入分量的頂點，在反向圖上跑一趟 DFS。這趟 DFS 所抵達的每個頂點，恰好構成一個 SCC。
- 重複直到堆疊清空；你切出來的這些群組就是強連通分量。
為什麼「按完成時間遞減彈出、並在反向圖上搜尋」能一次隔離一個 SCC？完成時間最大的那個頂點，住在縮圖的一個「源頭」SCC 裡——一個在原圖中沒有任何入向跨邊的分量。在反向圖裡那些跨邊指向相反方向，所以從那個頂點出發，你能到達它自己的分量、卻無法逃進任何別的分量，於是這趟 DFS 恰好舀起那一個 SCC 就停下。移除它，剩下頂點中完成時間最大的下一個未歸入頂點，又對剩餘部分扮演同樣的角色。每個分量都在一趟有界的搜尋中被找到，而整件事跑在 O(V + E)：兩趟線性的 DFS，加上翻轉邊的成本——在鄰接串列上這本身也是 O(V + E)。