你需要去上 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];     } }