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
| public class CourseSchedule {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int length = prerequisites.length;
if (numCourses < 2) {
return true;
}
int[] counter = new int[numCourses];
for (int[] prerequisite : prerequisites) {
counter[prerequisite[0]]++;
}
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++) {
if (counter[i] == 0) {
queue.add(i);
}
}
int ind = queue.size();
while (!queue.isEmpty()) {
int c = queue.poll();
for (int[] prerequisite : prerequisites) {
int crtC = prerequisite[0];
if (crtC == c) {
counter[crtC]--;
if (counter[crtC] == 0) {
ind++;
queue.add(crtC);
}
}
}
}
return ind == numCourses;
}
}
|