[LeetCode]210. Course Schedule II

Problem

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.

Solution

解析

主要考察拓扑排序。应用场景是课程学习过程，一门课在学习之前需要一些基础知识，循序渐进。比如说，修专业课之前，前两年必须先学点通用性的基础，比如高数、高物、英语等等。拓扑排序就是干这个的，确定一个序列，但是这个序列一般情况下并不唯一。

主要用于有向无环图。

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）：

每个顶点出现且只出现一次；
若A在序列中排在B的前面，则在图中不存在从B到A的路径。

拓扑排序算法：卡恩算法。

L ← 包含已排序的元素的空列表
S ← 没有进入边的节点（入度为零的节点）的集合
当 S 非空时：
    将节点n从S移走
    将n加到L尾
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
如 图有边 则：
    return error   (图至少有一个环)
否则： 
    return L   (以拓扑排序的顺序)

Code

这里图用邻接链表表示。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        if (numCourses <= 0) return {};
        vector<int> indegree(numCourses, 0);
        vector<vector<int>> graph(numCourses, vector<int>());
        
        for (auto p: prerequisites){
            graph[p[1]].push_back(p[0]);
            ++indegree[p[0]];
        }
        queue<int> zeroDegree;
        vector<int> res;
        for (int i= 0; i < numCourses; ++i)
            if (indegree[i] == 0)
                zeroDegree.push(i);
        
        while (!zeroDegree.empty()){
            int node = zeroDegree.front(); zeroDegree.pop();
            res.push_back(node);
            
            for (auto num : graph[node]){
                indegree[num]--;
                if (indegree[num] == 0)
                    zeroDegree.push(num);
            }
        }
        
        return res.size() == numCourses ? res : vector<int>();
    }
};