[LeetCode] 210. Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

课程表二。

题意跟207题几乎一样，要求返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。思路依然是拓扑排序。这一题我依然给出BFS的解法。同版本一一样，需要创建一个数组记录每个课程的入度，同时多维护一个指针 K = 0 和一个记录结果的数组res。遍历入度表，将入度为0的课程放入队列；并且每当加入一个入度为0的课程，K就++，原因是这些课程是没有先修课程的，可以放在一开始修。再遍历队列（记住队列里面都是没有先修课程的课），每弹出一个cur，就去检查这个cur是否是prerequisites某一个别的课程的先修课程，若是，则将这个别的课程的入度--；这里跟版本一一样，当有任何一个课程的入度被减至0，则将这个课程加入队列，同时也加入res。最后判断K是否跟课程总数一样，若是则说明所有的课程应该被遍历完了，返回课程顺序；若不是则说明课程安排里面有环，无法安排一个合理的顺序。

时间O(V + E)

空间O(n)

Java实现

 1 class Solution {
 2     public int[] findOrder(int numCourses, int[][] prerequisites) {
 3         int[] indegree = new int[numCourses];
 4         int[] res = new int[numCourses];
 5         // res用的指针
 6         int k = 0;
 7         // 取得所有的入度
 8         for (int[] pair : prerequisites) {
 9             indegree[pair[0]]++;
10         }
11 
12         Queue<Integer> queue = new LinkedList<>();
13         for (int i = 0; i < indegree.length; i++) {
14             if (indegree[i] == 0) {
15                 queue.offer(i);
16                 res[k] = i;
17                 k++;
18             }
19         }
20 
21         while (!queue.isEmpty()) {
22             int pre = queue.poll();
23             for (int[] pair : prerequisites) {
24                 if (pair[1] == pre) {
25                     indegree[pair[0]]--;
26                     if (indegree[pair[0]] == 0) {
27                         queue.offer(pair[0]);
28                         res[k] = pair[0];
29                         k++;
30                     }
31                 }
32             }
33         }
34         return (k == numCourses) ? res : new int[0];
35     }
36 }