科薩拉朱演算法（Kosaraju's algorithm）

科薩拉朱演算法找出有向圖所有的強連通分量——彼此相互可達的頂點群集——所用的不過是兩趟普通的深度優先搜尋。它的魅力在於概念上的清晰：它倚賴一個關於把所有箭頭反向的優雅觀察，而從那裡各分量幾乎像變魔術一樣浮現。只要你會跑 DFS，你就會跑科薩拉朱。

它分三步。第一，對整張圖跑 DFS，記下頂點完成的順序，每個頂點完成時把它推上一個堆疊。第二，把每條邊的方向翻轉，建出反向圖。第三，反覆從堆疊彈出頂點（於是你以完成時間遞減的順序處理它們），對每個尚未指派的頂點，在反向圖中跑一趟 DFS；那一趟反向 DFS 抵達的每個頂點，恰好構成一個強連通分量。為何行得通？關鍵事實是：把所有邊反向不改變 SCC（原圖中的來回，在每個箭頭翻轉後仍是來回），但它把 SCC 之間的單向橋以相反方向切斷。以完成時間遞減的順序處理頂點，意味你總是在凝聚 DAG 中位置「最晚」的那個 SCC 裡發起反向 DFS；因為反向圖中跨分量的邊都指向錯誤的方向、無法逃出，那趟反向 DFS 被困在一個 SCC 內並恰好淹沒它。以這個順序一層層剝下 SCC，使每次淹沒都侷限於單一分量。

科薩拉朱跑在 O(n + m)——兩趟線性 DFS 加上建反向圖——它是教學的最愛，因為每一塊都是你已經理解的普通走訪，巧思集中在「反向圖上的完成順序」這個想法。相對於塔揚演算法的實務提醒：科薩拉朱對圖做兩趟、且需要建構反向邊集，所以它碰資料兩次並為反向副本用掉額外空間，而塔揚在單趟 DFS 中就算出 SCC。同樣的大 O，但若你對一張巨大的圖只能跑一趟、或無法負擔儲存反向圖，塔揚是更精簡的選擇。