LeetCode Technology

LeetCode 207. Course Schedule

查阅更多的题解,请点击

Problem

Course Schedule

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, is it possible for you to finish all courses?

Solution

对于此类存在前后驱关系课程安排的问题,显然与拓扑排序相关:

  • 上述问题中,课程可以作为结点,课程间的关系作为边,可以构建出对应的有向图
  • 是否可以finish all courses则转换为了该有向图是否有一个拓扑排序的序列的问题(有向图在有回路的情况下是没有拓扑序列的)

由上述分析,该问题转化为判断图中是否存在环的问题。对于此类问题,显然DFS是最直观的做法,不过对于有向图而言,DFS判断是否存在环可行但不够高效,可以采用Kahn’s algorithm:

  • 将图中所有入度为0的点入栈
  • 取出栈顶元素,再弹栈,删除栈顶元素的作为前驱的所有边,若结点入度变为0,入栈,
  • 重复上述操作,直至栈空,若此时图中仍存在边,则该有向图至少有一个回路;否则,弹栈的顺序就是一个该图的一个拓扑排序

Note: 对于图中是否存在边的判断,可以变为在该过程中共有多少个顶点出栈:出栈顶点数=图的顶点数 =>结束后图中不存在边;出栈顶点数!=图的顶点数 =>结束后图中仍存在边

GitHub传送门

class Solution
{
  private:
    void makeGraph(int numCourses, vector<pair<int, int>> &prerequisites, vector<vector<int>> &graph, vector<int> &degrees)
    {
        for (auto pre : prerequisites)
        {
            graph[pre.second].push_back(pre.first);
            degrees[pre.first]++;
        }
    }
    bool topologicalSort(vector<vector<int>> &graph, vector<int> &degrees)
    {
        stack<int> noPre;
        for (int i = 0; i < degrees.size(); ++i)
        {
            if (degrees[i] == 0)
                noPre.push(i);
        }
        int count = 0;
        while(!noPre.empty()){
            int id = noPre.top();
            noPre.pop();
            count++;
            for(auto item:graph[id]){
                if(--degrees[item]==0)
                    noPre.push(item);
            }
        }
        return count == degrees.size();
    }

  public:
    bool canFinish(int numCourses, vector<pair<int, int>> &prerequisites)
    {
        vector<vector<int>> graph(numCourses, vector<int>());
        vector<int> degrees(numCourses, 0);
        makeGraph(numCourses, prerequisites, graph, degrees);
        return topologicalSort(graph, degrees);
    }
};

发表评论

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