給定一個有向無環圖（DAG），有
n個節點。找到最小的節點集合，使得從這些節點出發可以到達圖中所有節點。
Example:
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3]
Intuition
TIP
入度為 0 的節點無法從其他節點到達，必須被選為起點。
- 入度為 0 的節點不可能從任何其他節點到達
- 入度不為 0 的節點一定可以從某個入度為 0 的節點到達
- 因此答案就是所有入度為 0 的節點
Approaches
⭐ 1. Find Zero In-degree Nodes — O(V + E) / O(V)
- Idea: 計算每個節點的入度，收集入度為 0 的節點
- Time:
O(V + E) - Space:
O(V)
class Solution {
fun findSmallestSetOfVertices(n: Int, edges: List<List<Int>>): List<Int> {
val hasIncoming = BooleanArray(n)
for (edge in edges) {
hasIncoming[edge[1]] = true
}
return (0 until n).filter { !hasIncoming[it] }
}
}2. Use a Set — O(V + E) / O(V)
- Idea: 用 Set 記錄所有有入邊的節點，然後找出不在 Set 中的節點
- Time:
O(V + E) - Space:
O(V)
class Solution {
fun findSmallestSetOfVertices(n: Int, edges: List<List<Int>>): List<Int> {
val targets = edges.map { it[1] }.toHashSet()
return (0 until n).filter { it !in targets }
}
}🔑 Takeaways
- Pattern: DAG 入度分析 — 入度為 0 的節點是必選的起點
- Key trick: 這道題的關鍵洞察是：在 DAG 中，入度為 0 的節點集合就是最小覆蓋起點集合