首页
学习
活动
专区
圈层
工具
发布

判断有向图是否有圈

比如在众多的大学课程中,有些课有先修课,我们可以将其抽象为拓扑排序,有向边(v, w)表明课程v必须安排在w之前,否则课程w就无法进行。...虽然有圈图没有拓扑序列,但是我们可以利用拓扑排序的算法来判断一个有向图是否有圈。 算法描述如下: 1. 将所有入度为0的顶点放入队列; 2....否则,说明总     有顶点入度不为0,没有放入队列中,即该有向图有圈。...DFS 关于DFS的介绍请戳我,通过稍微修改DFS,利用递归的特点,也可以判断有向图是否有圈。...\n"); } return 0; }  上述利用DFS判断有向图是否有圈实际上是利用了深度优先生成树的性质:有向图无圈当且仅当其深度优先生成树没有回退边, 而上述算法中的vis[graph

3.3K80
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    判断链表是否有环

    判断一个单向链表是否有环。(指向表头结点的指针为head) 方法一: (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head (2)p1和p2分别采用1和2作为步长遍历该链表。...(注意,p2应该检查当前结点的下一个结点是否为NULL) (3)如果p1或者p2遇到了NULL,则证明该链表没有环;若p1和p2在某时刻指向同一结点,则说明该链表有环。...(fast == NULL || fast -> next == NULL); } (4)若该表有环, (a)设从表头结点(包括)开始到环开始的结点(不包括)共 有l1个结点;设从环开始结点(包括)到它们相遇的结点...第三种方法(通过修改链表,最终可还原链表,且可去掉链表中的环) 或许可以再构造了一个双向链,但不存储原来的数据而存储节点指针: typedef struct _PtrLinkNode { LinkNode...比较好的方法有两个: 一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。

    2K70

    Golang 是否有必要内存对齐?

    因为有内存对齐的存在,编译器使用了内存对齐,那么最后的大小结果就会不一样。至于为什么要做对齐,主要考虑下面两个原因: 平台(移植性) 不是所有的硬件平台都能够访问任意地址上的任意数据。...例如:特定的硬件平台只允许在特定地址获取特定类型的数据,否则会导致异常情况 性能 若访问未对齐的内存,将会导致 CPU 进行两次内存访问,并且要花费额外的时钟周期来处理对齐及运算。...需要注意的是,除了这个默认的对齐系数外,还有不同数据类型的对齐系数。数据类型的对齐系数在不同平台上可能会不一致。...79:11: struct of size 48 bytes could be of size 40 bytes (maligned) type SASL struct { ^ 提示有一处

    2.2K31

    java判断ExecutorService是否有任务

    有时候我们需要判断ExecutorService是否还有任务在执行或等待执行,以便进行相应的处理。本文将介绍如何判断ExecutorService是否有任务。1....判断ExecutorService是否有任务:一种简单的判断ExecutorService是否有任务的方法是使用`awaitTermination()`方法。...我们可以通过设置一个较短的超时时间来判断ExecutorService是否有任务。...System.out.println("ExecutorService has tasks: " + hasTasks);```上述代码将会等待1秒钟,如果在超时时间内有任务未完成,则返回true,表示ExecutorService有任务在执行或等待执行...总结:通过使用awaitTermination()方法并设置适当的超时时间,我们可以判断ExecutorService是否还有任务在执行或等待执行。希望本文对您有所帮助!

    10110

    链表是否有环,视频讲解

    Day 40:判断链表是否有环 1 链表有环是什么意思? 在判断是否有环前,需要先知道什么是链表中的环? 如下所示的链表有5个节点组成,框内的数字代表编号,也可理解为节点的地址。...注意区分地址值和链表的数据域是完全不同的: ? 节点0指向节点3,而节点10又指向节点3,所以节点3就是环的入口,形成如下所示的一个环: ?...所以,研究如何判断链表是否有环,是一个非常有意义的课题,也是面试中常考的。...2 如何判断链表是否有环 通过哈希的方法,代码比较好理解: class Solution(object): def hasCycle(self, head): s = set()...快慢指针判断链表是否有环,代码其实非常清晰,但是理解背后的数学原理,才是真正写出代码的关键,也就说一旦理解原理,就会很自然的写出代码;相反,如果不理解,仅仅凭记忆,那么时间长了,就容易忘记,面试时就容易写错

    80510

    A股指数图谱:是否有月份效应?

    获得投资经验有四种方法:实践、历史、理论和统计。大多数人是通过第一种,即实际操作,这是最重要的经验获取方法。...数据来源:使用tushare开源包获取上证指数、深证指数、沪深300、上证50、中小板和创业板1993-2018年数据,其中中小板和创业板是2011年-2018年数据。...“月份效应”检验思路:(1)将数据分成两组:m月份和其他月份;(2)检验两组数据的平均值是否相等。 源代码:Talk is cheap, show me the code (废话少数,放码过来!)...检验思路很简单:(1)将数据分成两组:m月份和其他月份;(2)检验两组数据的平均值是否相等。 各月份收益率描述性统计如下图: ?...各个月历史收益率的单样本t检验(检验均值是否异于0)、双样本t检验(检验某月份与其余月份收益率是否存在显著差异),结果如下表所示。

    1.2K40

    如何判断 Activity 上是否有弹窗

    今天来看个需求,如何判断 Activity 上面是否有弹窗,当然,简单的方式肯定有,例如在 Dialog show 的时候记录一下,但这种方式不够优雅,我们需要一款更通用的判断方式。...所以,我们只需要判断在 mView 集合中,两个 activity 之间是否有存在其他的 View,如果有,那就是有弹窗,开发步骤为: registerActivityLifecycleCallbacks...获取所有 Activity 的实例 传入想判断是否有弹窗的目标 Activity 实例,并获取该实例的 DecorView 拿到所有 Activity 实例的 DecorView 集合 遍历 mView...那有没有一种方法,可以直接遍历 mView 集合就能找到目标 Activity 是否有弹窗呢?还真有,那就是 AppToken。...第一种方案会判断失败,因为这时候的弹窗 View 在第一个 Activity 与 第二个 Activity 之间,所以,第二个 Activity 无法通过区间的方式判断到是否有弹窗 第二种方案判断成功

    3.7K20

    你是否知道Redis为什么有1️⃣6️⃣ 个数据库?

    这与在一个关系数据库实例中可以创建多个数据库类似(如下图所示),所以可以将其中的每个字典都理解成一个独立的数据库。 ?...二、正确理解Redis的“数据库”概念 ? 由于Redis不支持自定义数据库的名字,所以每个数据库都以编号命名。开发者则需要自己记录存储的数据与数据库的对应关系。...但是,要正确地理解Redis的“数据库”概念这里不得不提到一个命令: # 清空一个Redis实例中所有数据库中的数据 redis 127.0.0.1:6379> FLUSHALL 该命令可以清空实例下的所有数据库数据...比如可以使用0号数据库存储某个应用生产环境中的数据,使用1号数据库存储测试环境中的数据,但不适宜使用0号数据库存储A应用的数据而使用1号数据库B应用的数据,不同的应用应该使用不同的Redis实例存储数据...三、集群情况下是否支持一个实例多个db? ? 要注意以上所说的都是基于单体Redis的情况。而在集群的情况下不支持使用select命令来切换db,因为Redis集群模式下只有一个db0。

    1.2K60

    边缘计算容器化是否有必要?

    01 简要 由于容器有轻量级、安全性、秒级启动等优秀的特性,容器天然的轻量化和可移植性,非常适合边缘计算的场景,这一点边缘计算的厂家和开发者们都心知肚明。...我们经常能够看到“容器 + Kubernetes”的组合在DevOps发挥10X效率,最近也有越来越多Kubernetes运行在数据中心外(边缘)的需求。...边缘云平台将重点解决以下问题: 1、大规模 / 异构的设备,网关和边缘节点的接入; 2、大量遥测数据汇聚、处理后提供给云端应用使用; 3、设备安全和识别服务; 4、支持远程下达对设备的指令; 5、自动创建和管理边缘节点和设备...; 6、实现云端对边缘应用的编排、部署和配置; 7、为边缘应用的开发提供数据存储、事件管理、API 管理和数据分析等能力; 由于边缘云平台需要接入大量的IoT设备,并实现对这些设备的管理,而这些设备的数目可能是非常巨大的...Kubernetes作为开源的容器平台,拥有大量的社区文档和标准接口,而且Kubernetes满足了etcd数据库提供的持久化存储,事件处理、告警机制等要求,为边缘计算应用的开发、部署、调试提供了便利。

    3K30
    领券