企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文围绕「算法通关手册」仓库中 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$ 个节点的有向树上附加一条边后，只会出现以下两种「异常」：

1. 某个节点的入度为 2（有两个父节点，违反「除根外每个节点入度为 1」的约束）；
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.py：

class 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 核心思想

1. 用in_degree（哈希表）记录每个节点当前记录的父节点，用来定位入度为 2 的冲突边；
2. 用并查集在前向遍历中检测环；
3. 遍历结束后按三种情形分情况返回答案。

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已有父节点1，conflict_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已有父节点4，conflict_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 只需顺序遍历edges，当某条边两端已连通时直接返回该边；而 0685 因为引入了「入度 2」的冲突约束，答案既可能是冲突边、可能是环边、也可能是「冲突边中构成环的那条边」，判定逻辑显著复杂。

七、延伸思考：入度统计与有向图合法性

本题对「入度」的利用非常有代表性：入度为 0 的节点是唯一根，入度为 2 说明存在冲突。这一思想与拓扑排序中的入度统计一脉相承——仓库源码 Graph-Topological-Sorting-Kahn.py 中，Kahn 算法正是先统计所有节点入度，再不断移除入度为 0 的节点；若最终移除的节点数少于总节点数，则说明图中存在环，无法构成拓扑序列。

对照本题可以得出一个统一视角：有向无环图（DAG）的合法性 = 无环 + 恰当的入度结构。无论是拓扑排序、课程表问题，还是本题的冗余边删除，入度统计与并查集环检测都是最常用的两把钥匙。

小结

LeetCode 685「冗余连接 II」的核心收获有三点：

1. 明确有向树的合法性判据：唯一根（入度 0）+ 其余节点入度 1 + 无环；
2. 掌握并查集检测环的写法：顺序遍历边，两端已连通即成环；
3. 熟练处理「冲突 + 环」的组合判定：用in_degree记录首个父节点，最后依据三种情形返回正确边。

仓库中对应的 题解文档、并查集完整教程 与 并查集多种实现源码 可作为继续深入学习的入口。

• 教程
• 文档
• 知识库