教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕「算法通关手册」仓库中 0685. 冗余连接 II 题解 展开讲解如何在一棵有向树多出一条附加边后形成的「有向图」中找出唯一可删除的冗余边。全文以并查集Union Find为核心武器深入拆解「入度为 2 的冲突边」与「环」两类异常的组合判定并给出可直接运行的 Python 实现与复杂度分析。读完本文你将掌握处理「有向树合法性判定」类题目的通用套路并能复用到其他并查集场景。一、题目理解什么是有根树1.1 有根树的定义在本问题中有根树指满足以下条件的「有向」图该树只有一个根节点入度为 0没有父节点除根节点之外的每一个节点都有且只有一个父节点入度为 1。也就是说一棵有向树必须同时满足「入度约束」和「无环」两个条件。任一条件被破坏图就不再是有根树。1.2 输入图的性质输入是一个由 $n$ 个节点节点值不重复从 $1$ 到 $n$构成的树再附加一条有向边后形成的图。附加的边包含在 $1$ 到 $n$ 中的两个不同顶点间且不属于树中已存在的边。结果图以二维数组 $edges$ 表示每个元素是一对[ui, vi]表示「有向」图中从顶点 $ui$ 指向顶点 $vi$ 的边其中 $ui$ 是 $vi$ 的一个父节点。1.3 任务与约束要求返回一条能删除的边使得剩下的图是有 $n$ 个节点的有根树。若有多个答案返回最后出现在给定二维数组中的答案。说明$n edges.length$即边数等于节点数树有 $n-1$ 条边加上 1 条附加边恰好是 $n$ 条$3 \le n \le 10^{3}$$edges[i].length 2$$1 \le ui, vi \le n$。1.4 示例解析示例 1输入edges [[1,2],[1,3],[2,3]] 输出[2,3]节点 $1$ 是根指向 $2$ 和 $3$附加边 $[2,3]$ 让节点 $3$ 的入度变为 2父节点既有 $1$ 又有 $2$属于「入度为 2 的冲突边」。示例 2输入edges [[1,2],[2,3],[3,4],[4,1],[1,5]] 输出[4,1]节点 $1$ 的入度变为 2$4 \to 1$ 与附加边本身同时 $1 \to 2 \to 3 \to 4 \to 1$ 构成环属于「冲突边与环并存」的情形。二、解题突破口两类异常情况在一棵 $n$ 个节点的有向树上附加一条边后只会出现以下两种「异常」某个节点的入度为 2有两个父节点违反「除根外每个节点入度为 1」的约束图中存在环附加边把两个已经连通的祖先与后代节点直接相连。更细致地分答案的判定会落入以下三种情形之一情形冲突边入度为 2环应删除的边①无有直接删除构成环的那条边②有无直接删除造成入度为 2 的冲突边③有有删除「构成环的那条入度为 2 的边」即冲突边中真正导致环的那一条原题解给出的算法正是围绕这三种情形展开的用并查集检测环并记录入度为 2 的节点。三、并查集检测环的核心工具3.1 为什么用并查集并查集Union Find是一种高效管理「不相交集合」合并与查询的数据结构核心操作只有三个合并union(x, y)把 $x$、$y$ 所在的两个集合合并查找find(x)找到 $x$ 所在集合的代表元素根节点连通性判断is_connected(x, y)判断 $x$ 与 $y$ 是否同属一个集合。在无向/有向图场景中如果我们依次把每条边的两个端点「合并」进同一集合那么在添加某条边之前若两个端点已经连通这条边就必然构成环。这正是 0684无向图版与本题共用的核心原理。仓库 并查集教程文档 系统讲解了并查集的来龙去脉并给出多种实现快速查询基于数组ids[i]直接存储元素所属集合编号查询 $O(1)$但合并需遍历数组为 $O(n)$对应源码 tree_unionFind_QuickFind.py快速合并基于森林fa[x]指向父节点合并只需挂接根节点但最坏情况下树退化成链查找退化到 $O(n)$对应源码 tree_unionFind_QuickUnion.py隔代压缩 按秩合并路径压缩把查找路径上的节点直接挂到祖父节点按秩合并让深度小的树挂到深度大的树下单次操作均摊接近 $O(1)$对应源码 tree_unionFind_UnoinByRank.py。3.2 仓库推荐的精简实现文档 05_08_union_find.md 第 5 节指出实际刷题推荐「优先采用隔代压缩一般情况下无需引入按秩合并」代码如下见仓库源码 tree_unionFind.pyclass UnionFind: def __init__(self, n): # 初始化 self.fa [i for i in range(n)] # 每个元素的集合编号初始化为数组 fa 的下标索引 def find(self, x): # 查找元素根节点的集合编号内部实现方法 while self.fa[x] ! x: # 递归查找元素的父节点直到根节点 self.fa[x] self.fa[self.fa[x]] # 隔代压缩优化 x self.fa[x] return x # 返回元素根节点的集合编号 def union(self, x, y): # 合并操作令其中一个集合的树根节点指向另一个集合的树根节点 root_x self.find(x) root_y self.find(y) if root_x root_y: # x 和 y 的根节点集合编号相同说明 x 和 y 已经同属于一个集合 return False self.fa[root_x] root_y # x 的根节点连接到 y 的根节点上成为 y 的根节点的子节点 return True def is_connected(self, x, y): # 查询操作判断 x 和 y 是否同属于一个集合 return self.find(x) self.find(y)本题题解为了追求代码最简把并查集内联进了Solution类find采用「完全压缩」的递归写法parent[x] find(parent[x])将路径上所有节点直接挂到根节点与文档中的「完全压缩」实现一一对应两者原理相同、效果等价。四、算法流程详解并查集解法4.1 核心思想用in_degree哈希表记录每个节点当前记录的父节点用来定位入度为 2 的冲突边用并查集在前向遍历中检测环遍历结束后按三种情形分情况返回答案。4.2 完整代码含逐步注释class Solution: def findRedundantDirectedConnection(self, edges: List[List[int]]) - List[int]: n len(edges) parent list(range(n 1)) # 并查集父节点数组节点编号 1 ~ n下标 0 闲置 def find(x): if parent[x] ! x: # 完全压缩递归查找根节点 parent[x] find(parent[x]) # 并把路径上的节点直接挂到根节点下 return parent[x] def union(x, y): parent[find(x)] find(y) # 把 x 的根节点挂到 y 的根节点下 # 记录每个节点的父节点第一个父节点 in_degree {} conflict_edge None # 冲突边使某个节点入度变成 2 的那条边 cycle_edge None # 环边并入并查集前两端已连通的那条边 for u, v in edges: # 如果 v 已经有父节点说明出现入度为 2 的冲突 if v in in_degree: conflict_edge [u, v] # 只记录“最后出现”的冲突边 else: in_degree[v] u # 记录 v 的第一个父节点 u # 检查是否形成环 if find(u) find(v): # u、v 已经连通再加这条边必成环 cycle_edge [u, v] else: union(u, v) # 否则把 u、v 并入同一集合 # 情况 1没有冲突边只有环 —— 直接删除环边 if not conflict_edge: return cycle_edge # 情况 2有冲突边但没有环 —— 直接删除冲突边 if not cycle_edge: return conflict_edge # 情况 3既有冲突边又有环 # 环是由“v 的第一个父节点指向 v”的边 冲突边中的某一方共同造成的。 # 由于冲突边在并入前没有检测环真正构成环的是 # in_degree[conflict_edge[1]] - conflict_edge[1] # 删除这条“第一个父边”即可同时解除冲突与环。 return [in_degree[conflict_edge[1]], conflict_edge[1]]4.3 逐情形验证情形 ①只有环没有冲突边。例如edges [[1,2],[2,3],[3,1]]遍历到[3,1]时1、3已连通cycle_edge [3,1]且全程无conflict_edge直接返回[3,1]。情形 ②只有冲突边没有环。例如示例 1 的[[1,2],[1,3],[2,3]]in_degree {2: 1, 3: 1}遍历到[2,3]时发现3已有父节点1conflict_edge [2,3]此时所有边均不构成环返回[2,3]。情形 ③冲突边与环并存。例如示例 2 的[[1,2],[2,3],[3,4],[4,1],[1,5]]。遍历顺序[1,2]、[2,3]、[3,4]依次合并均不成环[4,1]到来前1尚无父节点in_degree为空于是in_degree[1] 4但find(4) find(1)都归属于同一连通块cycle_edge [4,1]且不执行合并[1,5]到来时发现1已有父节点4conflict_edge [1,5]。此时同时存在conflict_edge [1,5]与cycle_edge [4,1]。注意冲突边[1,5]在记录时并没有走并查集合并与环检测分支因为v已有父节点时直接跳过真正导致环的是「1的第一个父边」in_degree[1] 4即[4,1]。因此返回[4,1]与题目要求的输出一致。关键点在情形 ③ 中不能简单地返回cycle_edge或conflict_edge而必须返回[in_degree[conflict_edge[1]], conflict_edge[1]]——这条边既是冲突边的一员指向入度为 2 的节点又是环的组成部分删掉它能同时修复两类异常。五、复杂度分析时间复杂度$O(n \times \alpha(n))$其中 $n$ 是边的数量$\alpha(n)$ 是阿克曼函数的反函数可以认为是常数。单条边上的find/union操作均摊接近 $O(1)$整体接近线性。空间复杂度$O(n)$需要使用并查集数组和哈希表存储节点的父节点信息。该结论与仓库 并查集算法分析 一节给出的「$m$ 次操作总复杂度为 $O(m \times \alpha(n))$、空间 $O(n)$」完全一致。六、与 0684「冗余连接」无向图版的对比仓库中同时收录了 0684. 冗余连接 题解两题看似同源解法却存在本质差异对比维度0684无向图0685有向图图的方向无向有向合法性条件无环有唯一根、除根外入度均为 1、无环异常种类仅环一种冲突边入度 2 环两种可能组合算法核心边成环即删需区分三种情形决定删哪条边难度中等困难0684 只需顺序遍历edges当某条边两端已连通时直接返回该边而 0685 因为引入了「入度 2」的冲突约束答案既可能是冲突边、可能是环边、也可能是「冲突边中构成环的那条边」判定逻辑显著复杂。七、延伸思考入度统计与有向图合法性本题对「入度」的利用非常有代表性入度为 0 的节点是唯一根入度为 2 说明存在冲突。这一思想与拓扑排序中的入度统计一脉相承——仓库源码 Graph-Topological-Sorting-Kahn.py 中Kahn 算法正是先统计所有节点入度再不断移除入度为 0 的节点若最终移除的节点数少于总节点数则说明图中存在环无法构成拓扑序列。对照本题可以得出一个统一视角有向无环图DAG的合法性 无环 恰当的入度结构。无论是拓扑排序、课程表问题还是本题的冗余边删除入度统计与并查集环检测都是最常用的两把钥匙。小结LeetCode 685「冗余连接 II」的核心收获有三点明确有向树的合法性判据唯一根入度 0 其余节点入度 1 无环掌握并查集检测环的写法顺序遍历边两端已连通即成环熟练处理「冲突 环」的组合判定用in_degree记录首个父节点最后依据三种情形返回正确边。仓库中对应的 题解文档、并查集完整教程 与 并查集多种实现源码 可作为继续深入学习的入口。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐Dify工作流中图片显示的技术挑战与架构化解决方案Dify工作流中图片显示的技术挑战与架构化解决方案 在构建基于Dify平台的智能工作流时图片显示问题往往成为开发者面临的核心技术障碍之一。不同于传统的Web应示例工程AlgoNote 算法通关手册LeetCode 305 岛屿数量 II 并查集动态连通性解法详解AlgoNote 算法通关手册LeetCode 305 岛屿数量 II 并查集动态连通性解法详解 本篇技术指南以「算法通关手册」项目中的 0305. 岛屿数量教程文档知识库Posting 主题定制完全指南从内置主题到 YAML 自定义、语法高亮与 Xresources 换肤Posting 主题定制完全指南从内置主题到 YAML 自定义、语法高亮与 Xresources 换肤 Posting 是一款运行在终端里的现代化 API 客开发工具CLI上一篇如何在普通PC上构建完整的macOS系统OpenCore黑苹果配置深度解析下一篇GBFR-Logs终极指南3大功能揭秘如何通过实时DPS分析提升你的《碧蓝幻想Relink》战斗表现创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考