【leetcode】207. 课程表（course-schedule）（拓扑排序）[中等]

链接

https://leetcode-cn.com/problems/course-schedule/

耗时

解题：32 min
题解：10 min

题意

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

思路

拓扑排序。
使用先决条件建图，0->1 的有向边表示 0 依赖于 1，即想要学习课程 0 ，需要先完成课程 1。然后，每次找是否存在出度为 0 的节点，即不依赖于任何课程，删除这个节点及所有与这个节点相关的边，直到不存在出度为 0 的节点。最后判断图中是否还存在节点，如果存在则说明图中有环，不可能完成所有课程，否则可以完成。

时间复杂度： O ( V + E l o g E ) O(V+ElogE) O(V+ElogE)

AC代码

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<set<int>> E(numCourses);
        // [0,1] 0->1
        for(int i = 0; i < prerequisites.size(); ++i) {
            E[prerequisites[i][0]].insert(prerequisites[i][1]);                        
        }
        // topological sorting
        vector<bool> vis(numCourses, false);
        while(true) {
            bool flag = true;
            for(int i = 0; i < numCourses; ++i) {
                if(!vis[i] && E[i].empty()) { // node-> == 0
                    vis[i] = true;
                    for(int k = 0; k < numCourses; ++k) {
                        E[k].erase(i);
                    }
                    flag = false;
                    break;
                }
            }
            if(flag) break;
        }
        for(int i = 0; i < numCourses; ++i) {
            if(!vis[i]) 
                return false;
        }
        return true;
    }
};