207/210 Course Schedule I / II
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
题意：I 是给一串数组代表课程，并且这些课程有前置课程的要求。问是否能够完成所有课程。 II 是要求输出顺序。
经典的拓扑排序。 拓扑排序的两个步骤， 1. 按照关系建图 2. bfs 把度为 0 的节点入站。并且把其相关系的读书减一。 最后只要查一下度的数组是否全为 0 即可。 注意拓扑排序的复杂度是 O(V+E)
代码： 这里直接给出 II 的代码
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] ret = new int[numCourses];
int index = 0;
if(numCourses == 0 || numCourses == 1) return new int[]{0};
int[] degree = new int[numCourses];
for(int i = 0; i < prerequisites.length; i++) {
degree[prerequisites[i][0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < degree.length; i++) {
if(degree[i] == 0) {
queue.add(i);
ret[index++] = i;
}
}
while(!queue.isEmpty()) {
int cur = queue.poll();
for(int i = 0; i < prerequisites.length; i++) {
if(prerequisites[i][1] == cur) {
degree[prerequisites[i][0]]--;
if(degree[prerequisites[i][0]] == 0) {
queue.add(prerequisites[i][0]);
ret[index++] = prerequisites[i][0];
}
}
}
}
for(int i = 0; i < degree.length; i++) {
if(degree[i] != 0) return new int[0];
}
return ret;
}
}