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 方法在效能上有什麼實際差異？