力扣(LeetCode)207.课程表(C++)-创新互联-成都创新互联网站建设

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

力扣(LeetCode)207.课程表(C++)-创新互联

拓扑排序

根据示例看出,课程表是否存在环,是问题的关键。这题的环,和数组、链表的环不一样,不好判,要转化成图判拓扑序列。

目前创新互联已为上千多家的企业提供了网站建设、域名、虚拟空间、网站托管运营、企业网站设计、长白网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

考虑向右和向左的方向,拓扑序列的所有边可以指向同一方向。

无环图进行重排序,以及延展后,可以生成拓扑序列。考虑有环的性质 : 即使环外的边已经有序,环内至少有一条边是反向的,无法生成拓扑序列。

拓扑排序 : 队列里维护可以构造拓扑序列的点,每次将入度 ① _① ①​ 为 0 0 0 的点入队(在图中删除),相邻点的入度减一。如果有环的话,由于环的路径依赖,环内所有点都会有一个无法删除的前驱(入度至少为 1 1 1 ),这些点无法入队。完成拓扑排序后,如果所有点入队,则无环,否则有环。

名词解释

①入度 : 对于有向图的某个点,箭头指向这个点的边数,就是这个点的入度。

提示
  • d d d 保存所有点的入度。
  • g g g 保存所有点的出边,便于在删除某个点之后,维护这个点的出边的入度
拓展知识(可忽略)
  • 没入队的某些点形成了环。
  • 如果所有点入队,队列维护的点的顺序,刚好组成图的一个拓扑序列(不唯一)
题目描述

dd

核心代码
class Solution {public:
    bool canFinish(int n, vector>& p) {vector>g(n);
        vectord(n);
        for(auto &e:p) {g[e[1]].push_back(e[0]);
            d[e[0]]++;
        }
        queueq;
        for(int i = 0;iauto edge = q.front();
            q.pop();
            for(auto &e:g[edge])
                if(0==--d[e])
                    q.push(e);
            ans++;
        }
        return ans == n;
    }
};
  1. 时间复杂度 : O ( n + m ) O(n+m) O(n+m) , n n n 是有向图的结点数, m m m 是边数,无环图要遍历所有点和邻边,时间复杂度 O ( n + m ) O(n+m) O(n+m) 。
  2. 空间复杂度 : O ( n + m ) O(n+m) O(n+m) , 维护入度和出边的数组,空间复杂度 O ( n + m ) O(n+m) O(n+m) ,队列的最坏空间复杂度 O ( n ) O(n) O(n),总体空间复杂度 O ( n + m ) O(n+m) O(n+m) 。
AC

AC

致语
  • 理解思路很重要!
  • 欢迎读者在评论区留言,墨染看到就会回复的。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文标题:力扣(LeetCode)207.课程表(C++)-创新互联
链接URL:http://kswsj.cn/article/cscgod.html

其他资讯