你需要去上n门九章的课才能获得offer，这些课被标号为 0 到 n-1 。
有一些课程需要“前置课程”，比如如果你要上课程0，你需要先学课程1，我们用一个匹配来表示他们： [0,1]
给你课程的总数量和一些前置课程的需求，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
在线评测地址：领扣题库官网
例1:
输入: n = 2, prerequisites = [[1,0]]
输出: [0,1]例2:
输入: n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]解题思路
对于两门课之间的约束关系，很容易联想到图，我们可以将课抽象为节点，将约束抽象为一条有向边，可以用有向图的相关算法解决问题。拓扑排序正好可以解决这一问题。
算法：拓扑排序
一个合法的选课序列就是一个拓扑序，拓扑序是指一个满足有向图上，不存在一条边出节点在入节点后的线性序列，如果有向图中有环，就不存在拓扑序。可以通过拓扑排序算法来得到拓扑序，以及判断是否存在环。
拓扑排序步骤：
1.建图并记录所有节点的入度。
2.将所有入度为0的节点加入队列。
3.取出队首的元素now，将其加入拓扑序列。
4.访问所有now的邻接点nxt，将nxt的入度减1，当减到0后，将nxt加入队列。
5.重复步骤3、4，直到队列为空。
6.如果拓扑序列个数等于节点数，代表该有向图无环，且存在拓扑序。
复杂度分析
设课程数，即图的节点数为V。
约束数量，即图的边数为E。
时间复杂度O(V + E)
- 建图，扫描一遍所有的边O(E)。
- 每个节点最多入队出队1次，复杂度O(V)。
- 邻接表最终会被遍历1遍，复杂度O(E)。
- 综上，总复杂度为O(V + E)。
空间复杂度O(V + E) - 邻接表占用O(V + E)的空间。
- 队列最劣情况写占用O(V)的空间。
- 综上，总复杂度为O(V + E)。
public class Solution {
/*
* @param numCourses: a total of n courses
* @param prerequisites: a list of prerequisite pairs
* @return: the course order
*/
public int[] findOrder(int numCourses, int[][] prerequisites) {
List[] graph = new ArrayList[numCourses];
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<Integer>();
}
// 建图
for (int[] edge: prerequisites) {
graph[edge[1]].add(edge[0]);
inDegree[edge[0]]++;
}
int numChoose = 0;
Queue queue = new LinkedList();
int[] topoOrder = new int[numCourses];
// 将入度为 0 的编号加入队列
for(int i = 0; i < inDegree.length; i++){
if (inDegree[i] == 0) {
queue.add(i);
}
}
while (! queue.isEmpty()) {
int nowPos = (int)queue.poll();
topoOrder[numChoose] = nowPos;
numChoose++;
// 将每条边删去，如果入度降为 0，再加入队列
for (int i = 0; i < graph[nowPos].size(); i++) {
int nextPos = (int)graph[nowPos].get(i);
inDegree[nextPos]--;
if (inDegree[nextPos] == 0) {
queue.add(nextPos);
}
}
}
if (numChoose == numCourses)
return topoOrder;
return new int[0];
}
}
