LeetCode210-课程表II

LeetCode210-课程表II

拓扑排序

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
public static int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses == 0) return new int[0];
int[] inDegrees = new int[numCourses];
// 建立入度表
//prerequisites = [[1,0],[2,0],[3,1],[3,2]]
for (int[] p : prerequisites) { // 对于有先修课的课程,计算有几门先修课
inDegrees[p[0]]++;
}
// 入度为0的节点队列
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegrees.length; i++) {
if (inDegrees[i] == 0) queue.offer(i);
}
int count = 0; // 记录可以学完的课程数量
int[] res = new int[numCourses]; // 可以学完的课程
// 根据提供的先修课列表,删除入度为 0 的节点
while (!queue.isEmpty()){
int curr = queue.poll();
res[count++] = curr; // 将可以学完的课程加入结果当中
for (int[] p : prerequisites) {
if (p[1] == curr){
inDegrees[p[0]]--;
if (inDegrees[p[0]] == 0) queue.offer(p[0]);
}
}
}
if (count == numCourses) return res;
return new int[0];
}