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 {
int N = (int) 1e4 + 10, M = 4 * N;
int[] he = new int[N], e = new int[M], ne = new int[M];
int idx;
int[] cnt = new int[N];
private void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
Arrays.fill(he, -1);
for (int i = 0; i < n; i++) {
for (int j : graph[i]) {
add(j, i);
++cnt[i];
}
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (cnt[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int i = he[cur]; i != -1; i = ne[i]) {
int j = e[i];
if (--cnt[j] == 0) queue.offer(j);
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (cnt[i] == 0) ans.add(i);
}
return ans;
}
}
|
wechat
