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
41
42
43
44
45
46
| public class CourseScheduleII {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses < 1) {
return new int[0];
}
int[] result = new int[numCourses];
if (prerequisites == null || prerequisites.length == 0) {
while (numCourses > 0) {
result[numCourses - 1] = numCourses - 1;
numCourses--;
}
return result;
}
int[] counter = new int[numCourses];
for (int[] val : prerequisites) {
counter[val[0]]++;
}
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++) {
if (counter[i] == 0) {
queue.add(i);
}
}
int courseCanTake = queue.size();
int index = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
result[index++] = course;
for (int[] val : prerequisites) {
if (val[1] == course) {
counter[val[0]]--;
if (counter[val[0]] == 0) {
courseCanTake++;
queue.add(val[0]);
}
}
}
}
return (courseCanTake == numCourses) ? result : new int[0];
}
}
|