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
| public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
return true;
}
int[] indegree = new int[numCourses];
for (int[] pre : prerequisites) {
indegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
Integer currId = queue.poll();
numCourses--;
for (int[] pre : prerequisites) {
if (pre[1] == currId) {
indegree[pre[0]]--;
if (indegree[pre[0]] == 0) {
queue.offer(pre[0]);
}
}
}
}
return numCourses == 0;
}
|