type
status
date
slug
summary
tags
category
icon
password
时隔好久又来刷题了,大概率要寄了,这次刷到图论相关的，虽然比较简单，但是更好入门,也是学习了
📝 发现环
首先有几个名词
- 入度：指向某个顶点的边的数量。
- 出度:从某个顶点出发指向其他顶点的边的数量
延伸出来，度就是这个点有几根线连起来
- 顶点（Vertex）：图中的一个节点。
- 边（Edge）：连接两个顶点的线，可以有方向，也可以有权重。
- 邻接表：为每个顶点维护一个列表，列出所有与之直接相连的顶点
这里可以用vector实现，类似二维数组，每个顶点的值作为下标，每个下标下存储相连顶点
思路
根据度的概念，我们可以想到当有环存在的时候，度肯定不是1，也就是说与之相连的边不止一条,所以我们只需要找到度为1的顶点，删掉这个点，剩下的就是环了
代码实现：存储图,记录顶点的度
代码实现：删除度为1的顶点并删除跟其他顶点相连的边
🤗 总结归纳
这题目主要考验对图的简单应用
有关题目或文章的问题，欢迎您在底部评论区留言，一起交流~
- Author:小彦同学
- URL:https://alicization.site/article/2024/03/17/29440ce9-25c7-4879-93a7-5aad3fd188ef
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
