Tag: 图论

2023
算法图论

Floyd算法

摘要: Floyd算法的原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 历届图灵奖得主基本上都有高学历、高学位，绝大多数有博士头衔。这是可以理解的，因为创新型人才需要有很好的文化素养

算法图论

迪杰斯特拉算法(Dijkstra)

摘要: 迪杰斯特拉算法原理与代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 迪杰斯特拉（Edsger Wybe Dijkstra）在一个充满科学气息的家庭背景中长大，父亲

算法leetcode

力扣952-按公因数计算最大组件大小

摘要: 本文详细拆解 力扣952-按公因数计算最大组件大小。分解质因数+并查集 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们来看一个数论与并查集结合的问题，综合性比较强。 $1 题

2022
算法动态规划

【树形DP】树的直径

摘要: 力扣 1245, 1522，树的直径，最经典的树形 DP 题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，我们继续研究力扣秋季赛的题目。在十一之前参加了力扣秋季赛个人赛，

算法leetcode

力扣1162-多源BFS与多源最短路径

摘要: 力扣 1162，最基础的多源 BFS 题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 上个周日照例参加了力扣秋季赛的个人赛，在文章 2022力扣秋季赛个人赛战报 中记录的战报，并

算法leetcode

【DP难题】力扣1595-连通两组点的最小成本

摘要: 力扣 1575，比较难的图论题，抽象之后是最小边覆盖问题，有状态压缩DP和二分图最大匹配两种解法。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 今天我们来看一个比较难的图论题，力扣

算法图论

二分图匹配-最大匹配

摘要: 二分图最大匹配的算法：匈牙利算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于一个无向图 G，有 N 个节点(N >= 2)，可以发分成 A, B 两个非空集合，其中 $A \c

算法数据结构

用数组模拟链表的方式实现【带权有向图的邻接表】

在文章 邻接表 中，我们学习了邻接表及其应用，在文章 用数组模拟双向循环链表 中，我们学习了用数组模拟的方式实现链表，并用该链表解决了实际问题，同时 结合链表容易删除的特点使用逆向思维 中也介绍了一个思路完全一样的题目，也是用数组模拟链表解决的。 邻接表中的链表实际上也可以用数组模拟的方式来实现，本文我们就来看一下带权有向图的邻接表用数组模拟的实现方式。 带权有向图的邻接表在一个有 n 个点，m

算法疑难杂症

LCP04-覆盖

摘要: LCP04，状态压缩DP和二分图匹配两种解法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 今天我们来看一个比较难的图论题，力扣 LCP04。有状态压缩 DP 和二分图最大权匹配两种解法。之

算法基础算法

大学基础算法笔记

摘要: 大学算法课笔记 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 大学基础算法笔记，2017年，共 52 页。 算法基础 基本特性 计数与渐进 分治与递归 算法设计 动态规划 贪心 随机化

数图论

图论导引

摘要: 《图论导引》West 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文介绍一本偏数学的图论的书，研究生时期关注过，但是看了一章多就烂尾了。但是这本书还是非常好的，这里放

数优化

最优化算法(运筹学)的内容

摘要: 运筹学的主要内容 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 最优化算法，也就是优化计算，也是运筹学。关注点在于最优化问题的算法及其应用。主要内容包括规划论、库存论、图

2021
算法图论

图论算法理论,实现与应用

摘要: 《图论算法理论，实现与应用》 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 图论算法理论-实现及应用

算法图论

图论题目汇总

本文总结了力扣上 2000 题以内的关于图论的 40 道题。将场景相同的放到了一起。 图论是数学的一个分支，以图为研究对象。图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 在计算机中，图论算法提供的是一种对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基

数概率

【Puzzle】用户一次游戏带来的收入

摘要: 来自朋友的面试的概率题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 写在前面概率面试题连载已经写了几期了，目前的题目主要是《Fifty challenging problems i

算法图论

并查集-加边过程中维护具体连通分量

问题背景并查集回炉 基础并查集功能和题目列表: 并查集 带权并查集功能和题目列表: 带权并查集 并查集维护平面点的横纵坐标 并查集时光倒流 对于用[带权]并查集解决加边连通性的问题，我们之前处理过以下几类问题: 加边过程中动态地处理【两个点 x, y 是否连通】的查询问题 加边过程中动态地处理【某个点 x 对应的连通分量的大小】的查询问题 加边过程中动态地处理【当前连通分量的个数】的查询问题

2020
算法leetcode

【搜索难题】力扣1258-近义词句子

大杂烩：DFS + 哈希表 + 并查集 + 排序 $1 题目题目链接1258. 近义词句子 题目描述给你一个近义词表 synonyms 和一个句子 text ， synonyms 表中是一些近义词对 ，你可以将句子 text 中每个单词用它的近义词来替换。 请你找出所有用近义词替换后的句子，按 字典序排序 后返回。 提示：123450 <= synonyms.length &

算法leetcode

【搜索难题】力扣465-最优账单平衡

DFS 回溯 剪枝 $1 题目题目链接465. 最优账单平衡 题目描述一群朋友在度假期间会相互借钱。比如说，小爱同学支付了小新同学的午餐共计 10 美元。如果小明同学支付了小爱同学的出租车钱共计 5 美元。我们可以用一个三元组 (x, y, z) 表示一次交易，表示 x 借给 y 共计 z 美元。用 0, 1, 2 表示小爱同学、小新同学和小明同学（0, 1, 2 为人的标号），上述交易可以

算法动态规划

二次扫描与换根DP

摘要: 无根树上的树形DP，二次扫描与换根的处理方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 树形DP 中，我们简要介绍了树形 DP 的思想，以及列举了很多可以解决的问题。 在有的问题

算法动态规划

有向图上的DP(HMM前向后向计算)

$0 有向图上的 DP (HMM前向后向计算)一些表现形式为有向图 D 上的动态规划的问题，其阶段的推导是在 G 上进行的，如果本阶段在节点 u，u, v 之间没有有向边，则下一个阶段是无法到 v 的。 一般情况下图的节点不直接作为阶段，而是作为阶段持有的状态。而阶段另有一个维度表示，并且具有例如长度，时间这样的意义。DP 方程具有以下形式 12dp[v][i] = f(v, i, dp

算法动态规划

无向图上的DP(CRF前向后向计算)

$0 无向图上的 DP (CRF前向后向计算)一些表现形式为无向图 G 上的动态规划的问题，其阶段的推导是在 G 上进行的，如果本阶段在节点 u，u, v 之间没有无向边，则下一个阶段是无法到 v 的。 一般情况下图的节点不直接作为阶段，而是作为阶段持有的状态。而阶段另有一个维度表示，并且具有例如长度，时间这样的意义。DP 方程具有以下形式 12dp[v][i] = f(v, i, dp

算法图论

DAG判定

$0 场景给定有向图 D，判定 D 是否为 DAG 分析等价于判定有向图 D 中有没有环，因此判定 DAG 的算法与有向图判定环的算法相同。以下为复习。 有向图判定环的方法：有向图的环 BFS (拓扑排序) 如果拓扑排序后的排序列表长度小于 n，则无法拓扑排序，即 D 不是 DAG。 代码模板1234567891011121314151617181920212223242526class

算法图论

并查集维护平面点的横纵坐标

并查集 带权并查集 并查集维护坐标点的办法 维护点编号 维护横纵坐标 求连通分量个数的一种方法：枚举点，将代表元插入哈希表，由哈希表执行去重 947. 移除最多的同行或同列石头 1267. 统计参与通信的服务器 $0 场景二维平面有 N 个点，每个点有一个坐标 (x, y)，每两个点，如果横坐标相同或纵坐标相同，则视为在同一个连通分量中。问给定的 N 个点构成多少个连通分量。 (1) 并

算法图论

并查集时光倒流

并查集 带权并查集 并查集时光倒流 803. 打砖块 $0 并查集时光倒流对于维护加边连通性的过程，并查集是非常有力的。 但是由于并查集合并后一般是不支持回滚的，仅仅可以通过开栈的方式实现撤销合并，即回滚一步。 因此如果要维护一个删边连通性的过程，并查集就无法完成了。但是有些问题可以逆向思维，即正向思维是 初态图 -> 删边 -> 终态图，逆向思维就变成了 终态图 -> 加边

算法图论

下标索引堆优化Prim

1135. 最低成本联通所有城市 邻接表 + 二叉堆 Prim 最小生成树 $O(E\log E)$ 邻接表 + 下标索引堆 Prim 下标索引堆 在下标索引堆模板的基础上的修改 $O(E\log V)$ 完整代码 $0 1135. 最低成本联通所有城市$1 邻接表 Prim 参考: 最小生成树 123456将 0 加入集合 Twhile 尚有点没有进入集合 T 从剩下的点中

算法数据结构

邻接表

摘要: 邻接表的应用：桶、开散列表、树和图的存储 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们总结一下邻接表的各种应用。包括桶、开散列表、树和图的存储。 $0 邻接表邻接表可以看成带有索引

算法leetcode

【图论难题】力扣1632-矩阵转换后的秩

第 212 周赛 D 题 并查集维护连通分量整体的权值 带集合级权的并查集 拓扑排序 $1 题目题目链接 1632. 矩阵转换后的秩 题目描述给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的秩。 每个元素的 秩 是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规

算法数据结构

下标索引堆

背景 - 哈希索引堆及其优化 二叉堆 堆的标记删除 哈希索引堆 哈希索引堆的索引优化 下标索引堆 内部树形索引 外层哈希索引 代码 测试: 239. 滑动窗口最大值 索引堆优化邻接矩阵 Prim $0 背景(1) 支持按 key 删除的堆一般的堆不支持按key操作，例如按 key 删除，按 key 修改。 现实中这种需求是常见的，例如进程调度的时候，进程 ID 和进程优先级在一个堆中

算法leetcode

【设计难题】力扣631-设计Excel求和公式

基于图论的设计 $1 题目题目链接631. 设计 Excel 求和公式 题目描述你的任务是实现 Excel 的求和功能，具体的操作如下： Excel(int H, char W): 这是一个构造函数，输入表明了 Excel 的高度和宽度。H 是一个正整数，范围从 1 到 26，代表高度。W 是一个字符，范围从 ‘A’ 到 ‘Z’，宽度等于从 ‘A’ 到 W 的字母个数。Excel 表格是一个

算法动态规划

DAG上的DP

拓扑序(DFS 序 / BFS 序) 转移 dp[u] = f(dp[v]), u, v 是拓扑序的关系 按照 BFS 拓扑序推导还是按照 DFS 拓扑序推导需要根据需求来分析。 BFS 拓扑序 DP dp[v] := 以 v 为终点... 拓扑序: 计算 dp[v] 时，所有父节点 u 的 dp[u] 已经计算完 DFS 拓扑序 DP (记忆化搜索) dp[u] := 以 u 为起点...

吐槽挖坑区

最小生成树2

摘要: 最小生成树的一些衍生问题，比较难。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 最小生成树方案数 题目: P4208 最小生成树计数算法: Kruskal题解参考: 力扣1489-找

算法leetcode

力扣1489-找到最小生成树里的关键边和伪关键边

第 194 场周赛 D 题 枚举所有边分类 必出现在 MST 可以出现在 MST 不会出现在 MST 分类算法 step1: 删除边，跑 Krudkal，如果不连通(返回-1)或者 MST 变大，为必选边 step2: 选该边再跑 Krudkal，若 MST 变大，为必不选边，否则为可选边 优化： 在 Kruskal 基础上，将相同权的边放在一起考虑 Trajan算法: 无向图的桥

算法图论

DAG典型应用-活动网络

活动网络 AOV 网络 拓扑排序 AOE 网络 关键路径算法 建图，超级源，超级汇 超级源到超级汇的单源单汇最长路径 BFS 拓扑序 DP 预处理各节点信息求关键活动 【模板: AOE 网络求关键活动】 PTA 7-11 关键活动 $0 活动网络活动网络(activity network)是一种 DAG，可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安

算法图论

有向图的必经点,支配树

摘要: 有向图的必经点，支配树 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个从业务场景中抽象出来的图论的问题：有向图的必经点。给定有向图上的两个点 S 和 T，从

算法图论

k短路

K 短路 178. 第K短路 问题给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。 注意： 每条最短路中至少要包含一条边。 数据格式 第一行包含两个整数N和M。接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。 12341 <&

算法图论

基于 Floyd 搜索有向图的所有最小环

搜索有向图最小环长度并返回一个最小环 无向图的环 有向图的环 Floyd 搜索有向图所有的最小环 应用：854. 相似度为 K 的字符串 注: 最小环的问题也可以用 dijkstra 求解 $1 求有向图最小环长度并返回一个最小环有向图的环的基本概念参考：有向图的环 无向图 Floyd 求最小环的过程参考 无向图的环，有向图的情况类似。 考虑 Floyd 的过程： 在最外层 k 在迭代过

算法leetcode

【搜索难题】力扣854-相似度为K的字符串

有向图的环 建图 Ref: 官解 一个有重边和自环的图，按照规则改变内部的边，使得所有的边都是自环 规则：当某个位置的字符不相等时，需要一步交换，这步交换涉及到图中两条边的改动 长为 l 的环可以用 l - 1 次按照规则对边的修改得到 l 个自环(Ref: 置换群中的一个 l 循环 $(1,2,…,l)$ 可以用 l - 1 次对换变为 $(1),(2),(3),…,(l)$) 将图分解为多个

算法搜索

双向搜索

双向搜索的思想 双向BFS 双向迭代加深 $1 双向搜索的思想在一些问题中，初态和终态都是确定的，并且从初态想终态搜索，并且两个方向的搜索是等效的，和从终态向初态搜索都可以覆盖整个搜索空间，相当于搜索路径可逆。此时可以采用双向搜索。 在搜索过程中对状态染色，一共有三种： 未访问过 属于初态搜索树 属于终态搜索树 当属于初态的搜索树和属于终态的搜索树在某个状态相遇了，则搜索到了答案，此时根

算法图论

建图的CornerCase

摘要: 建图的各种 Corner Case 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们通过一个拓扑排序的应用问题，看一下在建图时可能遇到的各种 Corner Case。此外本题还有一个值

算法leetcode

【搜索难题】力扣126-两次搜索,搜索路径

搜索过程记录路径的方法 两次搜索 双向 BFS 优化: 枚举点找边改成枚举边找点 $1 题目题目链接126.单词接龙 II 题目描述给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则： 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明: 1234

算法图论

DFS序,欧拉序,dfn序

DFS序,欧拉序,dfn序的定义和性质 经典问题 $1 DFS序,欧拉序,dfn序的定义和性质(1) DFS 序定义DFS 过程中对于某节点进入这个节点的子树和离开子树的顺序 性质 满足每个节点都会在dfs序上出现恰好两次 任意子树的 dfs 序都是连续的 记节点 x 在 dfs 序中的两次出现的位置为 L[x], R[x]，则区间 [L[x], R[x]] 就是以 x 为根的子树的 d

算法图论

二分图判定

摘要: 本文介绍欧拉路径的判定定理、算法、代码模板和例题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 图论1-基本概念 中我了解了二分图的定义和一些性质。 本文我们以力扣第 785 题为

算法图论

差分约束

差分约束模型问题差分约束系统是一种特殊的 N 元一次不等式组，有 N 个变量 $X_{1} ~ X_{N}$ 以及 M 个约束条件。 每个约束条件室友两个变量做差得到的： X_{i} - X_{j} \leq c_{k} \\ c_{k} 为常数，1 \leq i,j \leq N, 1 \leq k \leq M问题：求出一组解 $X_{i} = a_{i}, i=1,2,…,N$，使得 M

算法图论

负环

摘要: 负环 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 负环在图论中，如果一条边的权值是负数，则为负权，如果图中存在一个环，还上各个边的权值之和为负数，则为负环。 在 带权图最短路径 中，各种单

算法图论

DFS拓扑排序

BFS 拓扑排序 DFS 的后序遍历实现拓扑排序 代码与 DFS 判定有向图的环几乎一样: 有向图的环 类似的算法：有向图的连通分量 对有向图进行 DFS，访问节点顺序的逆序就是一个拓扑排序结果。因此可以在 DFS 的回溯阶段将当前节点加入到遍历到的节点的列表中，相当于 DFS 后序遍历。 但这里有一个问题有如果有向图有环，照样可以 DFS 产生一个访问节点顺序的逆序。解法是在进行 DFS

算法图论

基环树

基环树概念 基环树常见处理方式 N 个点的树有 N - 1 条边，在树上任意加一条边，会形成一个环，除了环之外，其余部分由若干子树构成。 这种 N 个点 N 条边的连通无向图称为基环树。若干基环树组成的森林，为基环树森林。 有向图也有类似概念，N 个点，N 条边: 每个节点有且仅有一条入边的有向图，称为外向树。 每个节点有且仅有一条出边的有向图，称为内向树。 基环树结构在图论中也算比较

算法图论

超级源

摘要: 超级源的处理技巧 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 超级源和超级汇是图论问题中的一个处理技巧。本文我们简要介绍一下超级源和超级汇的思想，然后解决力扣 1168。

算法图论

最小生成树

1135. 最低成本联通所有城市 Kruskal 算法 切分定理以及 Kruskal 算法贪心的正确性 Kruskal 可以顺便判环 Prim 算法 邻接矩阵 $O(V^{2})$ 邻接表+堆 $O(E\log E)$ 超级源 $1 Kruskal 算法算法12345cost = 0循环 n - 1 次 (选 n - 1 条边): 按照 w 从小到大枚举边 edge &#

算法图论

有向图的环

有向图判定环 207. 课程表 DFS BFS(拓扑排序) 维护环的长度 最小环 经过特定点的最小环 有向图判定环207. 课程表 dfs在无向图判定环时，找到一个点，它不是 prev 点而又在此前遍历过，则形成环 有向图：以前遍历过并不代表形成环，办法是标记当前搜索路径，当回溯后，相应点要从标记中去掉。 123visited[i] = 0 未考查过visited[i] &

算法图论

无向图的环

无向图判定环 DFS 染色 BFS 染色 并查集 拓扑排序 返回一条在环上的边/判定具体的边是否在环上 684. 冗余连接 维护环的长度 d[u] := u 到源点 start 的距离 / d[i][j] := i 到 j 的距离 1559. 二维网格图中探测环 无向带权图最小环问题：344. 观光之旅 其它 环的计数 返回所有简单环 对环做缩点 $1 无向图判定环(模板)