強連通分量（strongly connected components）

在一張單行道地圖上，能從 A 開到 B 並不代表你能從 B 開回 A。強連通分量捕捉的是彼此相互可達的地方：有向圖中一群極大的頂點，其中你能從每個頂點走到每個其他頂點並走回來，全都遵守箭頭方向。在同一個 SCC 內，你能在任兩個成員之間來回；在不同 SCC 之間，往來頂多是單向的。

精確地說，兩個頂點 u 與 v 屬於同一個強連通分量，若存在一條從 u 到 v 的有向路徑「且」存在一條從 v 回到 u 的有向路徑。這是一個等價關係（自反、依定義對稱、藉黏接路徑而遞移），所以它把頂點切成不相交的類別——也就是 SCC。一個美妙的結構事實隨之而來：若你把每個 SCC 縮成單一個超級頂點，所得到的超級頂點圖（稱為凝聚圖）永遠是一張 DAG——它沒有環，因為 SCC 之間若有任何環就會把它們合併成一個更大的 SCC。所以有向圖在粗略層級上是一張由強連通團塊構成的 DAG，每個團塊內部則是雙向可達的糾纏。計算 SCC 與這個凝聚圖，是理解有向圖大尺度形狀的標準第一步。

凡是有向的相互可達很重要之處，SCC 就會出現：行程之間的死鎖環、彼此互連的網頁群、2-SAT 蘊涵圖中被迫相等的變數、有循環依賴的模組。兩個線性時間演算法在 O(n + m) 內算出所有 SCC：科薩拉朱法（兩趟 DFS，一趟在原圖、一趟在邊反向的副本上）與塔揚法（單趟 DFS 追蹤 low-link 值）。要分清的誠實對比：無向連通分量只問你究竟能不能在兩個頂點之間往來，而 SCC 要求你能回得來——所以這兩個概念在有向圖上確實不同，一張無向看來是一個連通分量的圖，一旦你遵守箭頭，可能碎成許多個 SCC。