LeetCode

210. Course Schedule II

查阅更多的题解,请点击

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;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注