Problem
1. 题目简述
一共有n门课程需要修，分别是从0到n-1。有些课程需要进行先修课程，我们以数组的形式给出，例如：[0, 1]，就是说如果要修课，必须要上过1课。
现在给出numCourses门课程，和一个prerequisites数组，求给出一种拓扑排序的方式。
2. 算法思路
参考解法：花花酱LeetCode
和LeetCode 207. Course Schedule类似，基本一致，这里不再赘述，直接上解析。
BFS
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
// BFS
int[] inDegree = new int[numCourses];
Stack<Integer> zeroDegreeVertex = new Stack();
int res[] = new int[numCourses];
ArrayList<Integer>[] relations = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
relations[i] = new ArrayList();
}
for (int[] prerequisite : prerequisites) {
inDegree[prerequisite[0]]++;
relations[prerequisite[1]].add(prerequisite[0]);
}
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
zeroDegreeVertex.push(i);
}
}
int index = 0;
while (!zeroDegreeVertex.isEmpty() && index != numCourses) {
res[index] = zeroDegreeVertex.pop();
for (int vertex : relations[res[index]]) {
inDegree[vertex]--;
if (inDegree[vertex] == 0) {
zeroDegreeVertex.push(vertex);
}
}
index++;
}
if (index != numCourses) {
return new int[0];
}
return res;
}
}