Leetcode 207 课程表 (拓扑排序，判断有向图环)

2020-12-13 02:49

阅读：429

标签：count 不为 sites span etc public 有向无环图 amp 一个队列

定义一个队列Q，把入度为0的结点入队

若Q不为空，则取队首结点，删去所有从该点出发的边，并把这些边所到达结点的入度减一，若某个节点入度减为0，则将它入队

反复进行如上操作，直到队列为空。（当总的入队次数大于节点数时，跳出循环）

如果这时入过队的节点数恰好等于节点总数，则为有向无环图。否则有环。

class Solution {
public:
    static const int maxn = 10000;
    vectorint> gra[maxn];
    int co = 0;
    int count[maxn] = { 0 };  //入度
    bool canFinish(int numCourses, vectorint>>& prerequisites) {
        queueint> Q;
        for (int i = 0;i ) {
            gra[prerequisites[i][1]].push_back(prerequisites[i][0]);
            count[prerequisites[i][0]]++;
        }
        int co = 0;
        for (int i = 0;i )
            if (count[i]==0) {
                Q.push(i);
            }
        while (!Q.empty()) {
            int cur = Q.front();
            Q.pop();
            co++;
            if (co > numCourses)break;
            for (int i = 0;i ) {
                count[gra[cur][i]]--;
                if (count[gra[cur][i]] == 0) {
                    Q.push(gra[cur][i]);
                }
            }
            gra[cur].clear();
        }
        if (co == numCourses)return true;
        else return false;
    }
};

Leetcode 207 课程表 (拓扑排序，判断有向图环)

标签：count 不为 sites span etc public 有向无环图 amp 一个队列

原文地址：https://www.cnblogs.com/suuusu/p/11056514.html

上一篇：Python 推送RabbitMQ

下一篇：HTML 5

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Leetcode 207 课程表 (拓扑排序，判断有向图环)
文章链接：http://soscw.com/essay/26365.html

亲，登录后才可以留言！

Leetcode 207 课程表 (拓扑排序，判断有向图环)

评论

热门文章

推荐文章

最新文章

置顶文章