前往
大廳
主題

LeetCode - 1557. Minimum Number of Vertices to Reach All Nodes 解題心得

Not In My Back Yard | 2022-08-24 12:00:40 | 巴幣 0 | 人氣 133

題目連結:


題目意譯:
給定一個有向無環圖(Directed Acyclic Graph,DAG),其有著 n 個節點並編號為 0 到 n - 1。並給定一個陣列 edges,其中 edges[i] = [fromi, toi] 代表著有一條單向的邊是從節點 fromi 到節點 toi。

找到最小的節點集合,使得圖中所有節點可以從集合中的節點抵達。保證答案唯一。

注意,你可以按照任意順序回傳這些節點。

限制:
2 ≦ n ≦ 10 ^ 5
1 ≦ edges.length ≦ min(10 ^ 5, n × (n - 1) / 2)
edges[i].length == 2
0 ≦ fromi, toi < n
所以數對 (fromi, toi) 皆相異。



範例測資:
範例 1:
輸入: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
輸出: [0,3]
解釋:無法從單一一個節點到達所有節點。從 0 我們可以到達 [0,1,2,5]。從 3 我們可以去到 [3,4,2,5]。所以我們回傳 [0,3]。

範例 2:
輸入: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
輸出: [0,2,3]
解釋: 注意到節點 0 、 3 和 2 從其他節點是無法到達的,所以我們必須包含它們。而且這些節點可以抵達節點 1 和 4。


解題思維:
其實就是變相地在問「有哪些節點沒有「進入」其中的邊存在,也就是 in-degree 為零者」,因為從任一個節點開始回溯到可以抵達該節點的節點(們),然後再從這些節點繼續回溯……最終必定會落在若干個 in-degree 為零的節點上。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作