Categories: Graph/DFS

Level: Medium

寫在前面

(基礎+進階+面試篇)從 LeetCode 學演算法 + 面試成功指南**

(3591元有效期限至 2024/05/16 23:59)
https://hiskio.com/bundles/egb397?s=tc

(3990元 長期有效) https://bit.ly/lc2022all

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/lc2022adv

Question

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a ** safe node** if every possible path starting from that node leads to a ** terminal node** (or another safe node).

Return an array containing all the *safe nodes * of the graph. The answer should be sorted in ascending order.

Example 1

1
2
3
4
5

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Example 2

1
2
3
4

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

Constraints

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] is sorted in a strictly increasing order.
• The graph may contain self-loops.
• The number of edges in the graph will be in the range [1, 4 * 104].

分析/解題

有一個有向圖，當中包含了n個節點，每個節點分別被標記為0~n-1。
這個圖使用2D的array graph來表示，
當中graph[i]代表所有從節點i有邊(edge)相連的節點，
且方向是從節點i到每個graph[i]中的節點。

如果一個節點沒有任何向外的邊 的話，則該節點是terminal node ；
如果從一個節點出去的所有可能的路徑 都導向到terminal node 的話，
則該節點是safe node 。

試找出所有圖中的safe nodes，並且以陣列(串列)型態回傳，
當中答案必須要以升冪排序 (由小到大排列)。

首先我們要思考的是，怎麼樣的狀況下會沒辦法terminal呢？
按照定義，一旦導到terminal node ，則由於沒有向外的邊，
於是路徑就會停在terminal node了(因為無路可走 )。
換句話說，如果要不停下來的話，就要一直有路可走。
但節點和邊都是有限的 ，那麼就只有當存在環 的狀況下，
才能夠一直有路可以走囉！

因此，要判斷一個點是否為safe node，
端看從該點出發的路徑是否存在有環 ；
如果有環的話，則包含該點，以及環上的所有節點都不會是safe node 。

同時，由於我們判斷safe node必須要所有路徑 都沒有環存在，
因此前面檢查過的節點結果，會同樣適用於後面的檢查 。
例如：從點A出發，如果其中一條路徑我們走過點B跟點C，
那麼下次當檢查從點B出發的時候，
我們可以直接採納前面點A出發經過點B時對點B判斷的結果，
如此一來就不用重新再走一遍了！

那麼這題應該要做的就是遍歷每一個節點及路徑，
並且每條路徑都走到底(或者走到可以判定是否有環)為止，
這顯然適用於DFS的做法。

讓我們來試著列看看解題步驟：

1. 初始化兩個陣列(串列) vis, path ，分別代表該節點是否已造訪過，
   以及該節點是否為某個環的一部分，兩者的長度均為graph的節點數量n，
   預設值均為0(或False也可以)。
2. 初始化一個空的res串列備用。
3. 宣告一個dfs函式，代入curr, graph, vis, path (curr為要檢查的node)，
   其回傳True則代表存在環，False則代表不存在環 。
4. 在dfs函式中，進行以下處理：
   4–1. 將vis[curr]和path[curr]均設為1 (也就是已造訪，且暫定環存在 )
   4–2. 迴圈從graph[curr] 中取出節點u：
   4–2–1. 若vis[u]為0 (表示這個節點還沒被造訪) -> 
   代入到dfs往下檢查，如得到回傳True的話則也回傳True(代表確定有環)
   4–2–2. 否則，若path[u] == 1 (表示** u在環上**)，回傳True。
   4–3. 經過迴圈結束後尚未回傳，代表其實從curr往下走並不存在環，
   這時候重新將path[curr]設為0 ，並且回傳False 。
   (前面直接回傳True的時候，因為我們預先將沿路的path[curr]設為1，
   因此離開的時候整條路徑上的節點都被標記成環了 ；
   反過來說，當發現不存在環的時候，該還原的就要還原回來 。)
5. 在主函式中，使用迴圈令i依次從0~n-1 ，
   如果vis[i] == 0 的話，就代入進行dfs。
6. 都做完的狀況下，再次使用迴圈令i從0~n-1 ，
   將path[i] == 0 的i 加入到res。
7. 回傳res。

依此，寫成程式碼如下：

Java

Java的部分使用了ArrayList給res使用，
如果想要讓dfs不要帶入那麼多東西的話，
也可以將vis跟path設定為class variables，
不過因為長度跟graph的節點數掛勾，
所以還是要在eventualSafeNodes裡才能初始化。

Python

Python的部分如同以前提到過的，
使用子函式也可以稍微減少需要代入的變數量，
甚至將vis和path放最前面的話也可以連它們都不需要代入，
因為子函式可以去取得到上面這層的變數。
(讀者可以自行嘗試再改寫看看)

面試實際可能會遇到的問題

「時間／空間複雜度？」
(O(V+E)/O(V)，V為graph的節點數，E為graph的邊數)

「能不能只用一個陣列／串列來處理經過的節點和環？」
(提示：State可以不只有1或0，可以設定3種state來處理)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/lc2022base