#Problem

#⭐️⭐️⭐️⭐️

Find Eventual Safe States

#Solution

就是找cycle的问题. 去掉所有cycle中的结点,剩下的就是eventual safe states

#Performance

既然是找cycle,那就是O(n) time了.

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
final List<Integer> res = new ArrayList<>();
if (graph.length == 0) return res;
final int n = graph.length;
final Set<Integer> cycles = new HashSet<>();
final int[] visited = new int[n];
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
final List<Integer> tmpCycle = new ArrayList<>();
if (dfsCycle(i, graph, visited, tmpCycle)) {
cycles.addAll(tmpCycle);
}
}
}
for (int i = 0; i < n; i++) {
if (!cycles.contains(i)) {
res.add(i);
}
}
return res;
}
private boolean dfsCycle(final int v, final int[][] graph, final int[] visited, final List<Integer> tmpCycle) {
if (visited[v] == -1) return true;
if (visited[v] == 1) return false;
tmpCycle.add(v);
visited[v] = -1;
for (final int adj : graph[v]) {
if (dfsCycle(adj, graph, visited, tmpCycle)) {
return true;
}
}
visited[v] = 1;
tmpCycle.remove(tmpCycle.size() - 1);
return false;
}
}

Comments