leetcode 课程表 中等

本文主要是介绍leetcode 课程表 中等，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

拓扑。

存 prerequisties[1] 到 prerequisties[0] 的边，然后记录入度。

用队列来进行拓扑，边对应终点入度- 1，入度为 0 时，加入队列。

最后判断每个点是否入度为 0 即可。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edge(numCourses);   // edge[i] 存 边
        vector<int> in(numCourses, 0);     // 入度
        for(int i = 0; i < prerequisites.size(); ++ i) {
            edge[prerequisites[i][1]].emplace_back(prerequisites[i][0]);
            ++ in[prerequisites[i][0]];
        }
        queue<int> que;     //
        for(int i = 0; i < numCourses; ++ i) {
            if(in[i] == 0) {
                que.push(i);
            }
        }
        while(!que.empty()) {
            int f = que.front(); que.pop();
            for(int i = 0; i < edge[f].size(); ++ i) {
                -- in[edge[f][i]];
                if(in[edge[f][i]] == 0) {
                    que.push(edge[f][i]);
                }
            }
        }
        for(int i = 0; i < numCourses; ++ i) {
            if(in[i] != 0) return false;
        }
        return true;
    }
};

这篇关于leetcode 课程表 中等的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！