前往
大廳
主題

LeetCode - 802. Find Eventual Safe States 解題心得

Not In My Back Yard | 2022-11-05 12:00:22 | 巴幣 0 | 人氣 303

題目連結:


題目意譯:
現在有一個有著 n 個節點的有向圖,其中節點們編號為 0 到 n - 1。該圖以一個索引值從 0 開始的二維陣列 graph 所表示,其中 graph[i] 為一個整數陣列代表著節點 i 之相鄰節點,意即節點 i 有一條邊可以走到 graph[i] 中的每一個節點。

如果有一個節點沒有走出去的邊,則該節點為終端節點。如果有一個節點滿足所有從該節點出發的路徑必定都會導向至一個終端節點(或另一個安全節點)的話,則該節點稱為安全的。

回傳一陣列包含圖中所有的安全節點。答案應按照升序排序。

限制:
n == graph.length
1 ≦ n ≦ 10 ^ 4
0 ≦ graph[i].length ≦ n
0 ≦ graph[i][j] ≦ n - 1
graph[i] 以嚴格升序排序。
該圖可能包含自環(Self-loops)。
圖中的邊數位於範圍 [1, 4 × 10 ^ 4] 中。



範例測資:
範例 1:
Illustration of graph
輸入: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
輸出: [2,4,5,6]
解釋: 給定的圖如上圖所示。
節點 5 和 6 為終端節點,因為它們兩者皆無出去的邊存在。
每條從節點 2 、 4 、 5 和 6 出發的路徑,最終都會導向至節點 5 或 6。

範例 2:
輸入: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
輸出: [4]
解釋:
只有節點 4 是一個終端節點,而每一個從節點 4 開始的路徑終將都會導向到節點 4。


解題思維:
用兩個陣列 S 和 V 分別表示節點的資訊,前者代表節點是否安全、後者則是有沒有被探訪過。

接著掃過所有節點 0 ~ n - 1,然後對於尚未被探訪的節點(因為編號較後面的節點在這樣的順序下可能被前面的節點先探訪到)利用給定的陣列 graph 進行深度優先搜尋(Depth First Search,DFS)。

而在遞迴的時候(假設最一開始是在節點 i),根據題目的敘述我們可以看到 graph[i] 中所有節點遞迴下去都必須是安全的,節點 i 才會是安全的。所以如果遞迴之回傳結果有任何一者是「不安全」的,則節點 i 就「不安全」。

最後把所有是安全的節點按編號由小到大收集起來放進一個陣列之中即為所求。




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

創作回應

更多創作