每日一题【day2】

题目链接

思路：对于两门课之间的约束关系，很容易联想到图，我们可以将课抽象为节点，将约束抽象为一条有向边，可以用有向图的相关算法解决问题。拓扑排序正好可以解决这一问题。

算法：拓扑排序
一个合法的选课序列就是一个拓扑序，拓扑序是指一个满足有向图上，不存>在一条边出节点在入节点后的线性序列，如果有向图中有环，就不存在拓扑>序。可以通过拓扑排序算法来得到拓扑序，以及判断是否存在环。
拓扑排序步骤：
建图并记录所有节点的入度。
将所有入度为0的节点加入队列。
取出队首的元素now，将其加入拓扑序列。
访问所有now的邻接点nxt，将nxt的入度减1，当减到0后，将nxt加入队列。
重复步骤3、4，直到队列为空。
如果拓扑序列个数等于节点数，代表该有向图无环，且存在拓扑序。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        vector<unordered_multiset<int>> route(numCourses);
        vector<int> degree(numCourses, 0);
        for(int i = 0; i < prerequisites.size(); ++ i) 
        {
            route[prerequisites[i][1]].insert(prerequisites[i][0]);
            degree[prerequisites[i][0]] ++;
        }
        queue<int> qu;
        for (int i = 0; i < numCourses; ++i)
        {
            if (degree[i] == 0)
                qu.push(i);
        }
        int num=0;
        while (!qu.empty()) {
            int tmp= qu.front(); 
            qu.pop();
            num++;
            for(auto it = route[tmp].begin(); it != route[tmp].end(); ++ it) {
                degree[*it]--;
                if (degree[*it] == 0) 
                {
                    qu.push(*it);
                }
            }
        }
        return num == numCourses;
    }
};