題目與使用情境
圖有 n 個頂點和 m 條有向邊，頂點可能沒有出邊，邊可能重複，輸入不保證連通。強連通分量是頂點集合，其中任意兩個頂點都能互相到達。實作需要返回分量列表，並說明如何透過縮點得到有向無環圖。
面試官考察什麼
- 是否能正確維護 DFS 索引、
low值、堆疊和在堆疊標記。 - 能否解釋樹邊、返祖邊和指向已完成分量邊對
low更新的差異。 - 是否涵蓋非連通圖、自環、重邊和遞迴深度風險。
- 是否能給出 O(n+m) 時間與 O(n) 輔助空間，並說明測試不變量。
作答前的釐清問題
先確認頂點編號是否連續、是否允許重複邊、輸出分量內部是否需要排序，以及執行環境是否限制遞迴深度。再確認圖規模、是否需要線上增量更新、是否只需判斷兩個頂點是否同分量。若圖規模很大，我會說明遞迴版本與顯式堆疊版本的取捨。
30 秒回答框架
我會做一次 DFS，並為每個頂點分配遞增索引和目前可回溯到的最小索引 low。頂點入堆疊並標記在堆疊後，遍歷鄰居：未訪問鄰居先遞迴並用它的 low 更新目前值；仍在堆疊中的鄰居用其索引更新。若 low 等於自身索引，目前頂點就是分量根，從堆疊頂端彈到它為止。每條邊和頂點只被常數次處理，因此複雜度是 O(n+m)。
分步驟深入解答
- 初始化狀態。 為每個頂點準備索引、
low、在堆疊標記和元件編號；索引從 0 或 1 單調遞增。對所有未訪問頂點啟動 DFS，涵蓋非連通圖。 - 處理未訪問鄰居。 遞迴訪問鄰居後執行
low[u] = min(low[u], low[v])。這條更新代表透過 DFS 子樹能回到更早的堆疊頂端。 - 處理堆疊內鄰居。 若鄰居仍在堆疊中，用鄰居的索引更新
low[u]。已經彈出並歸屬其他分量的鄰居不能參與回溯，否則會把兩個分量錯誤合併。 - 識別根並彈堆疊。 當
low[u]等於index[u]時，u 是目前分量根。持續彈出堆疊並清除標記，直到彈出 u；被彈出的頂點共同組成一個強連通分量。 - 處理邊界。 自環會讓頂點保持為單點分量；重邊只會重複執行同一最小值更新；孤立頂點在入堆疊後立即成為單點分量。
- 驗證和縮點。 檢查每個頂點恰好屬於一個分量，並驗證元件間邊構成 DAG。隨機小圖可用傳遞閉包或 Kosaraju 結果對照，大圖再驗證複雜度與堆疊深度。
高品質示範回答
我會維護四個陣列：遞增的 index、回溯值 low、在堆疊標記和分量編號。DFS 進入頂點時分配 index 並入堆疊。遇到未訪問鄰居，遞迴結束後用鄰居的 low 更新目前頂點；遇到仍在堆疊中的鄰居，只用鄰居的 index 更新。已完成的分量不會參與更新。
當 low[u] == index[u]，u 是根，我從堆疊頂端彈出直到 u，得到一個分量並清除標記。對所有未訪問頂點啟動 DFS，所以不要求圖連通。每個頂點入堆疊和出堆疊一次，每條邊檢查一次，時間 O(n+m)，輔助空間 O(n)。測試會涵蓋自環、重邊、孤立點、長鏈、多個環和非連通圖，並檢查分量劃分和縮點 DAG。
常見錯誤
- 對所有已訪問鄰居都用其 low 更新，導致跨已完成分量錯誤回溯。
- 彈出分量後忘記清除在堆疊標記，使後續邊把舊頂點當作目前路徑。
- 只從一個起點 DFS，漏掉非連通圖中的分量。
- 把
low等於目前 index 誤解為沒有邊，而忽略它表示目前頂點是分量根。 - 遞迴深度超過語言堆疊限制卻沒有說明顯式堆疊、分塊輸入或執行期設定方案。
追問及應對
為什麼已經彈出的頂點不能更新 low？
它已經屬於一個完成的分量，不再是目前 DFS 路徑上的可回溯祖先。使用它的 low 會跨越分量邊界，破壞分量極大性。
如何證明每個分量只彈出一次？
每個頂點入堆疊一次，只有根條件成立時才從堆疊頂端彈出；彈出後在堆疊標記被清除，後續 DFS 不會再次入堆疊。因此每個頂點恰好歸屬一個分量。
Tarjan 與 Kosaraju 如何選擇？
Tarjan 一次 DFS、無需轉置圖，適合希望降低遍歷和儲存的實作；Kosaraju 用兩次 DFS，概念直觀且容易拆成獨立階段。兩者都能達到 O(n+m)，選擇應依據語言堆疊限制、程式可讀性和既有圖表示。