查阅更多的题解，请点击

Problem

210. Course Schedule II

Solution

设课程数为v，课程之间共有e个先修关系

拓扑排序, O(v+e) time

题目中已给出提示，可以将课程看做节点，课程的先修关系看做有向边，由此可以构造一个具有v个节点，e条边的有向图，由此，该问题就变成了一个经典问题：判断一个有向图中是否存在回路。若存在回路，则课程安排失败

判断一个图是否是有向无环图，可以考虑拓扑排序，如果能得到一个拓扑排序的结果，则其也是一个课程安排的结果：

a. 将图中所有入度为0的点入栈
b. 取出栈顶元素，再弹栈，此时访问节点数加一，删除栈顶元素的作为前驱的所有边（将相邻结点的入度减一），若结点入度变为0，入栈
c. 重复上述操作，直至栈空，若此时图中仍存在边（即结束后，访问结点数仍少于总的节点数），则该有向图至少有一个回路；否则，弹栈的顺序就是一个该图的一个拓扑排序

图采用邻接表存储，构建图和计算入度过程O(e) time, 整个拓扑排序过程实际上也是一个BFS的过程，时间复杂度为O(v+e) time。所以总的算法的时间复杂度为O(v+e) time.

GitHub传送门

class Solution
{

public:
    vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites)
    {
        vector<vector<int>> g(numCourses);
        vector<int> inDegree(numCourses, 0);
        for (auto item : prerequisites)
        {
            g[item[0]].emplace_back(item[1]);
            inDegree[item[1]]++;
        }

        stack<int> s;
        for (int i = 0; i < numCourses; ++i)
        {
            if (inDegree[i] == 0)
                s.push(i);
        }

        int visited = 0;
        vector<int> order;
        while (!s.empty())
        {
            int cur = s.top();
            s.pop();
            order.push_back(cur);
            visited++;
            for (auto node : g[cur])
            {
                if (--inDegree[node] == 0)
                    s.push(node);
            }
        }
        if(visited!=numCourses){
            vector<int> ret;
            return ret;
        }
        return order;
        }

private:
    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>> &prerequisites)
    {
        vector<vector<int>> g;
        for (auto item : prerequisites)
        {
            g[item[0]].emplace_back(item[1]);
        }
        return g;
    }
};