題目描述:給定一個有向圖,若一個節點出發的所有路徑最終都到達終端節點(沒有出邊的節點),則該節點為「安全節點」。回傳所有安全節點的列表(升序排列)。
解題思路:一個節點是安全的,當且僅當它不在任何環中。可以用 DFS 三色標記法:
時間複雜度: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),但實作較複雜。