Re: [閒聊] 每日LeetCode已回收
https://leetcode.com/problems/find-eventual-safe-states/description/
802. Find Eventual Safe States
給你一個編號為 0 到 n-1 的有向圖 graph，定義：
終端節點：沒有任何向外的邊。
安全節點：所有存在的路徑都通向終端節點。
找出圖中的所有安全節點編號，並依照編號順序排列。
Example 1:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/17/picture1.png
Illustration of graph
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:
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.
思路：
1.先找出所有出度為0的節點標記為安全節點。
2.對每個點進行DFS，如果每個路徑都是安全節點則該點也為安全節點，否則該點為
不安全節點，另外遇到任何cycle時該點也為不安全節點。
3.nodeState = 1 表示安全節點 nodeState = -1 表示不安全 nodeState = 0 表示未
統計的節點。
4.把節點都跑過之後，把nodeState = 1 的照順序轉成 List 即可。
Java Code：
-----------------------------------------------
class Solution {
private int[][] graph;
private int[] nodeState;
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
this.graph = graph;
this.nodeState = new int[n];
for (int i = 0; i < n; i++) {
if (graph[i].length == 0) {
nodeState[i] = 1;
}
}
for (int i = 0; i < n; i++) {
if (nodeState[i] == 0) {
dfs(i, new boolean[n]);
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (nodeState[i] == 1) {
res.add(i);
}
}
return res;
}
private boolean dfs(int id, boolean[] visited) {
if (nodeState[id] == 1) {
return true;
}
if (visited[id] || nodeState[id] == -1) {
return false;
}
visited[id] = true;
for (int next : graph[id]) {
if (!dfs(next, visited)) {
nodeState[id] = -1;
return false;
}
}
nodeState[id] = 1;
return true;
}
}
-----------------------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689177574.A.F2E.html
※ 編輯: Rushia (122.100.75.86 臺灣), 07/13/2023 00:01:48
※ 編輯: Rushia (122.100.75.86 臺灣), 07/13/2023 00:02:41
→
07/13 00:05,
2年前
, 1F
07/13 00:05, 1F
討論串 (同標題文章)
完整討論串 (本文為第 365 之 719 篇)：