Description
在有向圖中，從某節點出發，若無論走哪條路徑最終都會到達終端節點（出度為 0），則該節點是安全節點。回傳所有安全節點（升序排列）。
Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]] Output: [2,4,5,6]
Intuition#
安全節點 = 不在任何環上的節點。用 DFS 標記環上節點，或用反向拓撲排序。
- 終端節點（出度 0）一定安全
- 所有路徑都指向安全節點的節點也是安全的
- 在環上的節點一定不安全
Approaches#
1: DFS 三色標記#
- 概念: 用三種狀態（未訪問/處理中/安全）做 DFS。若 DFS 遇到「處理中」節點代表有環，該路徑上的節點不安全。
- 時間複雜度:
O(V + E) - 空間複雜度:
O(V)
class Solution {
fun eventualSafeNodes(graph: Array<IntArray>): List<Int> {
val n = graph.size
// 0: 未訪問, 1: 處理中, 2: 安全
val state = IntArray(n)
fun dfs(node: Int): Boolean {
if (state[node] != 0) return state[node] == 2
state[node] = 1
for (next in graph[node]) {
if (!dfs(next)) return false
}
state[node] = 2
return true
}
return (0 until n).filter { dfs(it) }
}
}⭐2: 反向圖拓撲排序#
- 概念: 建立反向圖，從終端節點（原圖出度 0）開始拓撲排序，能被處理到的節點都是安全的
- 時間複雜度:
O(V + E) - 空間複雜度:
O(V + E)
class Solution {
fun eventualSafeNodes(graph: Array<IntArray>): List<Int> {
val n = graph.size
val outDeg = IntArray(n)
val reverseGraph = Array(n) { mutableListOf<Int>() }
for (u in 0 until n) {
for (v in graph[u]) {
reverseGraph[v].add(u)
}
outDeg[u] = graph[u].size
}
val queue = ArrayDeque<Int>()
for (i in 0 until n) {
if (outDeg[i] == 0) queue.add(i)
}
val safe = BooleanArray(n)
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
safe[node] = true
for (prev in reverseGraph[node]) {
outDeg[prev]--
if (outDeg[prev] == 0) queue.add(prev)
}
}
return (0 until n).filter { safe[it] }
}
}🔑 Takeaways#
- Pattern: 環偵測 / 拓撲排序 – 安全節點等同於不在環上的節點
- 關鍵技巧: DFS 三色標記法簡潔高效；反向圖拓撲排序利用出度為 0 的節點作為起點