Description
給定一個有向無環圖（DAG），有
n個節點。找到最小的節點集合，使得從這些節點出發可以到達圖中所有節點。
Example:
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]] Output: [0,3]
Intuition#
入度為 0 的節點無法從其他節點到達，必須被選為起點。
- 入度為 0 的節點不可能從任何其他節點到達
- 入度不為 0 的節點一定可以從某個入度為 0 的節點到達
- 因此答案就是所有入度為 0 的節點
Approaches#
⭐1: 找入度為 0 的節點#
- 概念: 計算每個節點的入度，收集入度為 0 的節點
- 時間複雜度:
O(V + E) - 空間複雜度:
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: 使用 Set#
- 概念: 用 Set 記錄所有有入邊的節點，然後找出不在 Set 中的節點
- 時間複雜度:
O(V + E) - 空間複雜度:
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 的節點是必選的起點
- 關鍵技巧: 這道題的關鍵洞察是：在 DAG 中，入度為 0 的節點集合就是最小覆蓋起點集合