MediumRating 1962
802. Find Eventual Safe States
depth-first-searchbreadth-first-searchgraphtopological-sort
解題說明
Find Eventual Safe States
題目描述:給定一個有向圖,若一個節點出發的所有路徑最終都到達終端節點(沒有出邊的節點),則該節點為「安全節點」。回傳所有安全節點的列表(升序排列)。
解題思路:一個節點是安全的,當且僅當它不在任何環中。可以用 DFS 三色標記法:
- 白色(0):未訪問。
- 灰色(1):正在訪問(在遞迴堆疊中)。
- 黑色(2):已確認安全。
- 對每個未訪問的節點進行 DFS。
- 進入節點時標記為灰色。
- 若遇到灰色節點,說明存在環,不安全。
- 若所有鄰居都被確認為安全(黑色),則當前節點也安全,標記為黑色。
C++ 解法
複雜度分析
時間複雜度:O(V + E) — 每個節點和每條邊最多被訪問一次(已著色的節點直接回傳)。
空間複雜度:O(V) — 狀態陣列和遞迴堆疊。
虛擬碼
1. Initialize state[0..n-1] = WHITE (0)
2. For each node i from 0 to n-1:
a. Call isSafe(i)
b. If safe, add to result
3. isSafe(node):
a. If state[node] != WHITE, return state[node] == BLACK
b. state[node] = GRAY
c. For each neighbor:
- If !isSafe(neighbor), return false
d. state[node] = BLACK
e. Return true
4. Return result其他解法
反向拓撲排序(BFS):建立反向圖,從所有終端節點(出度為 0)開始 BFS。將可到達的節點標記為安全。用入度(原圖的出度)追蹤,每次將入度減為 0 的節點加入佇列。時間 O(V+E),空間 O(V+E)(反向圖)。這個方法避免了遞迴,適合圖很大的場景。
SCC(強連通分量):用 Tarjan 或 Kosaraju 找所有 SCC,大小 > 1 的 SCC 中的節點都不安全。時間 O(V+E),但實作較複雜。
延伸思考
- 三色標記法中,灰色節點為什麼代表「在環中」?
- 如果要找出所有在環中的節點(而非安全節點),該如何修改?
- 反向拓撲排序的方法和 DFS 方法在效能上有什麼實際差異?