1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] g = new List[numCourses];
Arrays.setAll(g, k -> new ArrayList<>());
int[] in = new int[numCourses];
for (int[] p : prerequisites) {
int a = p[0], b = p[1];
g[b].add(a);
++in[a];
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; ++i) {
if (in[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int i = queue.poll();
--numCourses;
for (int j : g[i]) {
if (--in[j] == 0) queue.offer(j);
}
}
return numCourses == 0;
}
}
|
wechat
