1. 项目背景与核心问题拆解今天在算法营刷到第五十四天题目是“108. 多余的边”和“109. 多余的边II”。这两道题是典型的图论冗余连接问题核心工具是并查集Union-Find。如果你在准备后端面试或者正在刷LeetCode“多余边”这类题几乎是躲不开的——它考察的是你对无向图环的判断、有向图入度的理解以及对并查集这个数据结构的熟练程度。先说清楚这两道题到底在干嘛给定一个图原本是一棵树有n个节点、n-1条边现在多加了一条边让图变成了有环的图。你要找出那条多余的边把它删掉后恢复成树。第一道题是“多余的边”处理的是无向图第二道题是“多余的边II”处理的是有向图。无向图的解法相对直白利用并查集找环有向图则多了一层入度为2的判断需要分类讨论。很多新手刷到这里会懵为什么无向图只要用并查集就能找到环为什么有向图的解法突然复杂那么多因为无向图里环的判定等价于“两个节点在加这条边之前已经连通”而有向图里除了环还要处理“一个节点有两个父亲”的冲突。这两种情况需要分开考虑并且最终答案可能要删的边还不止一条候选。别担心这篇文章会把背后的原理、完整代码、以及我踩过的坑全部讲透适合刚学完图论基础、准备集中刷并查集题目的读者。2. 并查集基础与核心原理2.1 并查集到底解决什么问题并查集是一种管理元素所属集合的数据结构主要支持两种操作查找Find和合并Union。它的经典应用场景就是判断“两个节点是否在同一个连通分量里”以及“把两个连通分量合并”。你可以把它想象成一群人组队每个人最初都是独立的队伍队长就是自己。如果两个人认识就把两支队伍合并选一个人当队长。想知道两个人是否在同一个队伍只需要看他们的队长是不是同一个人。在无向图里依次遍历每条边如果边的两个端点已经在同一个集合里说明加上这条边就会形成环——那么这条边就是“多余的边”。这正是108题的核心思路。实现上我们需要一个数组parent来记录每个节点的父节点以及一个find函数来找到某个节点的根节点。2.2 路径压缩与按秩合并并查集如果每次查找都一层层往上爬最坏情况会形成一条链时间复杂度退化成O(n)。所以需要两个优化路径压缩在find的过程中把路径上所有节点的父节点直接指向根节点这样下次查找就是O(1)级别。按秩合并记录每个集合的“秩”通常是树的高度或节点数合并时把秩小的树挂到秩大的树上防止树变得过高。这两个优化写起来很简单但效果很关键。实际刷题中路径压缩基本必写按秩合并可选但加上后整个算法几乎能达到常数时间。2.3 模板代码这是我在刷题时固定使用的并查集模板直接抄下来就能用class UnionFind: def __init__(self, n): self.parent list(range(n 1)) # 节点编号从1开始 self.rank [0] * (n 1) def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False # 已经在同一个集合再合并就会成环 # 按秩合并 if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 return True注意这里的union返回值当两个节点已经在同一集合时返回False意味着当前这条边是多余的。这个设计在无向图题里非常顺手。3. 108. 多余的边无向图冗余连接解析3.1 题目理解题目会给你一个二维数组edges其中每个元素[ui, vi]表示节点ui和vi之间有一条无向边。整个图有 n 个节点并且原本是一棵树现在多加了一条边使得图中出现一个环。要求返回一条可以删除的边使得剩下的图仍然是一棵有 n 个节点的树。这里有几个关键细节如果有多个答案返回输入中最后出现的那条边题目要求。节点编号从 1 到 n。保证输入的图是连通的并且恰好有一个环。为什么要返回最后出现的那条因为按照顺序遍历第一次发现“两个端点已经连通”的边其实就是形成环的那条边。但你依次加边的时候如果在这条边之前已经形成了环那么那条之前的边才是真正导致环出现的边吗并不是。举个例子边 (1,2)、(1,3)、(2,3)。你依次遍历先加 (1,2) 连通再加 (1,3) 连通到 (2,3) 时发现 2 和 3 已经连通于是 (2,3) 是“最后出现”的使环形成的边。但实际删除 (1,3) 也能恢复树。题目要求返回最后出现的那条边正好就是当发现连通时当前正在处理的这条边。3.2 解题思路如何用并查集检测环思路很简单初始化一个大小为 n1 的并查集。遍历edges中的每条边[u, v]。调用union(u, v)如果返回True说明这条边连接了两个不同集合合并成功继续下一条。如果返回False说明两个点已经在同一个集合里这条边就是多余的直接返回[u, v]。因为题目保证只有一个环所以遍历完一定会有一次返回False。返回的那条边就是答案。这个方法的本质是如果两个节点在加这条边之前已经连通那么这条边就会形成一个环。一旦出现这种情况这条边就是多余的。3.3 完整代码与逐步注释下面是我提交通过的完整代码class UnionFind: def __init__(self, n): self.parent list(range(n 1)) self.rank [0] * (n 1) def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 return True class Solution: def findRedundantConnection(self, edges): n len(edges) uf UnionFind(n) for edge in edges: if not uf.union(edge[0], edge[1]): return edge return []这里有几个细节n直接用len(edges)即可因为树的边数是节点数减一多加一条边后边数等于节点数。节点编号从 1 开始所以parent数组长度为n 1下标 0 闲置。题目要求返回最后出现的多余边而我们的遍历顺序刚好是从头到尾第一次遇见环就返回这个边就是最后出现的那条其实更准确地说这个边是在当前遍历顺序中第一次使环闭合的边也就是题目定义的“最后出现”——因为之后的边都还没遍历呢。你可以理解为在输入顺序中这条边是让图成为有环图的最后一条边。如果怕绕可以换个角度你按顺序把边加进并查集直到某条边加不进去两端已连通那么这条边就是“最后出现”的多余边因为它之后没有边了。这样理解就顺了。3.4 复杂度分析时间复杂度O(n α(n))其中 α(n) 是阿克曼函数的反函数可以看作常数。因为有 n 条边每条边执行 find 和 union 操作路径压缩后近似 O(1)。空间复杂度O(n)用于存储 parent 和 rank 数组。这个复杂度非常优秀处理十万条边也毫无压力。4. 109. 多余的边II有向图冗余连接解析4.1 与上一道题的差别第二道题变成有向图了。输入同样是边数组但每条边[u, v]表示从u指向v的有向边。原本是一个有向树或者叫根树即除了根节点外每个节点有且只有一个入边根节点没有入边。现在多加了一条边导致有两种违规情况情况一某个节点入度变成 2。也就是有两个节点同时指向它。情况二形成了有向环。即使每个节点入度都正常也可能因为多加一条边导致环。注意情况一可能存在也可能与情况二同时存在。题目要求返回一条多余的边删除这条边后剩下的图仍然是一棵有向树。如果有多个答案返回输入中最后出现的多余边。这和无向图的“环”很不一样无向图只要发现两个端点已连通就是环有向图里哪怕所有节点入度都正常也可能存在环而且环的判定不能简单用并查集直接做因为方向性会导致逻辑变化。4.2 两种冲突情况的分类讨论我们先枚举所有可能没有节点入度为2但图中有环。这时多余的边就是构成环的那条边直接用并查集遍历第一次导致环的边就是答案。有一个节点入度为2。这时有两条候选边都指向该节点。我们需要删除其中一条。判断标准是删除哪条边之后剩余的图能成为一棵有向树如果删除候选边1后剩余图中没有环那么候选边1就是答案。如果删除候选边1后剩余图中仍有环那么答案就是候选边2。还有一种特殊情况两条候选边里有一条本身就在环上另一条不在那删除在环上的那条即可。这里有一个容易搞混的点入度为2的节点它的两条候选边可能一条是“真正的多余边”另一条是“原树里正常的边”。你要删除的是多余的那条。怎么判断呢最简单的办法是先假设删除第一条候选边比如输入中位置靠前的然后用并查集检查剩余图是否合法。如果合法删除第一条如果不合法说明第一条是必要的只能删除第二条。但这样直接做有个坑题目要求“返回最后出现的多余边”如果两种删除方案都可行呢实际上在有向树中如果入度冲突和环同时存在只有一种删除方案能让图变成树。如果不存在入度冲突只有环那么只有一条构成环的边是多余的。所以不会出现二义性。4.3 解题步骤先处理入度为2再处理环我推荐的解题流程先记录所有节点的入度。找到入度为2的节点记为node它的两条入边分别记为候选candidate1和candidate2按输入顺序candidate1在前candidate2在后。先尝试删除candidate1用并查集检查剩下的边是否能构成一棵有向树无环。如果可行答案就是candidate1。如果不可行答案就是candidate2。如果不存在入度为2的节点说明只存在环。此时按照无向图的方法顺序遍历边用并查集判断环第一次遇到两端已经在同一集合中的边就是答案。这里“检查是否可行”需要写一个辅助函数给定要删除的边把剩余所有边依次加入并查集一旦发现两条边的端点已经连通就说明有环不可行。为什么要“先删除第一条候选边”因为题目要求返回最后出现的多余边而candidate1在输入顺序中更靠前candidate2更靠后。因此如果删除candidate2合法其实也应该返回candidate2才对这里要仔细想。实际上候选边有两条都指向入度为2的节点。题目要我们删除“多余的边”这个多余边一定是在输入顺序中最后出现的吗不一定。它要求的是“如果存在多个答案返回最后出现的边”。也就是说可能有不止一条边删除后能让图变成树在这种情况下才需要返回最后出现的。但有向树的合法性要求很严格在一个有 n 个节点、n-1 条边的有向图中要成为一棵有向树必须满足只有根的入度为0其余节点入度为1从根出发可以到达所有节点等价于无环。如果入度冲突存在那么删除一条入边后另一个节点的入度变为1但可能仍然有环比如环中的边没有指向入度为2节点的。此时就需要继续检查环。所以最终可行的删除方案通常只有一个。不存在多个答案的情况除非有多个环但题意说只多加了一条边最多只能产生一个环和一个入度冲突所以最终答案唯一。那为什么题目还要说“如果有多个答案”这主要是针对无向图那道题的遗留说法在有向图这里实际上答案通常是唯一的。我们就按正常逻辑处理即可。因此更稳妥的做法是先判断是否存在入度为2的节点。如果存在就尝试删除其中一条检查剩余图是否合法如果不合法再删除另一条。两条都删除后一定有一个合法。如果不存在入度为2则直接找环。4.4 完整代码与关键细节下面是我调试通过的代码结构清晰class UnionFind: def __init__(self, n): self.parent list(range(n 1)) self.rank [0] * (n 1) def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 return True class Solution: def findRedundantDirectedConnection(self, edges): n len(edges) indegree [0] * (n 1) for u, v in edges: indegree[v] 1 # 找入度为2的节点以及对应的两条候选边 node -1 candidates [] for u, v in edges: if indegree[v] 2: node v candidates.append([u, v]) # 辅助函数删除 skip 这条边后是否能成为有向树 def is_valid_after_remove(skip): uf UnionFind(n) for u, v in edges: if [u, v] skip: continue if not uf.union(u, v): return False return True # 如果存在入度为2的节点 if node ! -1: # 先尝试删除第一条候选边输入靠前的 if is_valid_after_remove(candidates[0]): return candidates[0] else: return candidates[1] # 不存在入度为2的情况直接找环 uf UnionFind(n) for u, v in edges: if not uf.union(u, v): return [u, v] return []这个代码有几个关键细节值得说candidates中边的顺序正是输入中的顺序所以candidates[0]靠前candidates[1]靠后。is_valid_after_remove里用if [u, v] skip来判断跳过哪条边这种方法适用于边没有重复的情况。如果有重复边这种比较可能出错但本题保证不会出现完全相同的两条边所以安全。如果不存在入度为2的节点直接用并查集找环找到的第一条使环闭合的边就是答案。此时因为每个节点入度都为1但二叉树的边数是 n-1 吗注意这里边的总数是 n节点数也是 n。如果每个节点入度都是1必然存在环因为 n 个节点、n 条边的有向图不可能没有环且每个节点的出度至少为1不然根不存在。事实上这种情况下会恰好存在一个环并查集能找到它。4.5 复杂度分析时间复杂度O(n α(n))。虽然is_valid_after_remove里会遍历所有边但只调用两次每次都是 O(n α(n))所以总体还是 O(n α(n))。空间复杂度O(n)。这个解法已经是最优的了。LeetCode 上这个题的题解也大多采用类似思路。5. 实操中的常见问题与排查技巧5.1 并查集数组初始化错误这是我刷题时最常犯的错误parent数组长度没设成n 1直接用了n。因为节点编号从 1 开始如果你parent的长度是 n那么访问parent[n]就会越界。更隐蔽的是你用了 0 下标但题目没有 0 号节点导致一堆奇怪的错误。排查技巧创建并查集后马上打印parent数组确认长度并且写一个简单的find(1)和find(n)测试一下是否正常。养成这个习惯并查集相关的题能少踩很多坑。5.2 合并时忘记判断根union操作的正确顺序是先find两个节点的根如果根相同说明已经有路径返回False否则再合并。但新手容易在合并时直接写self.parent[x] y这其实是把 x 直接挂到 y 上没有经过根节点会破坏树的结构导致后续find出错。我曾经写过一段代码union里忘了调用find直接parent[x] y结果在无向图题目里当检测到环时返回的边经常不对因为并查集本身已经错乱了。所以一定要把模板写熟不要临时发挥。5.3 有向图情况下的候选边顺序问题109题里如果你找到了入度为2的节点两条候选边的顺序一定要按输入顺序存储。有些实现会用candidates []按遍历顺序append如果遍历顺序和输入顺序一致那没问题但如果先存了一个再覆盖另一个顺序就会颠倒。建议直接先完整遍历一遍边数组把所有指向该节点的边按顺序存下来。或者像我上面代码一样在遍历edges时遇到入度为2的节点的边就append因为第二次遍历edges的顺序就是输入顺序所以顺序一定是正确的。5.4 理解“最后出现的多余边”这句话108题里如果有多条边都可以删除要返回最后出现的那条。但实际上只要你按顺序遍历并用并查集检测第一次碰到环闭合的边就是“最后出现”的。因为在那条边之后如果有边它们还没加入所以这条边就是使图成为有环图的最后一条边——这里的“最后”是指能让图合法的最靠后的选择吗可以这样理解假设数组长度为 m你从前往后遍历当到达第 i 条边时发现环那么 1~i 条边构成了有环图而 1~i-1 条边无环。若删除第 i 条边图无环若删除前面某条边图仍可能有环但题目要求返回“最后出现”如果多条可行最后出现的是哪一条实际上在无向图中只会有一条边能删除后整个图无环吗不一定比如一个环里有三条边删除任意一条都能让图变树。但题目要求返回最后出现的边。按照并查集顺序遍历第一次构成环的边一定是环中最后出现的那条所以自然满足要求。所以这个实现是对的。对于109题如果存在入度为2答案可能在两条候选边中。如果两条候选边删除后都能让图变得合法那应该返回最后出现的那条。但这种情况会发生吗假设有入度冲突同时还有环那么两条候选边中只有边1删除后合法或者只有边2删除后合法。如果两条都合法说明原图没有环但原图边数是 n节点数是 n不可能没有环有向图 n 个点 n 条边必有环。所以不能两条都合法。如果原图没有环边数就应该是 n-1但原图边数是 n矛盾。所以实际上两条候选边删除后最多只有一条合法。因此顺序问题在109题里不影响答案但为了逻辑严谨还是按输入顺序存。5.5 一个容易忽略的边界条件109题中如果入度为2的节点存在你尝试删除第一条候选边后发现仍不合法返回第二条候选边时需要确保第二条候选边删除后确实合法。理论上一定合法但写代码时可以用is_valid_after_remove再验证一下以防万一。不过题目保证输入合法所以直接返回即可。还有一点如果节点编号不是从1开始呢那就需要先确认节点编号范围。这道题中节点编号从1到n所以直接用 n 没问题。如果遇到不连续的编号就要先离散化或改成用字典维护并查集。但 LeetCode 这两道题都明确编号从1开始所以不用处理。6. 从刷题到面试这类题怎么讲清楚很多读者问我刷了题但面试时怎么才能让面试官觉得我厉害对于并查集建议按这个顺序讲先说清楚问题给一个树多加一条边找多余边。说明为什么想到并查集因为需要判断“两个点是否已经连通”。解释并查集的两种优化路径压缩和按秩合并。无向图场景直接套模板。有向图场景先找入度为2的节点再尝试删除候选边最后检查环。如果你能直接在白板上写出上面两段代码并说明每一行在做什么面试官一般不会刁难你。更进阶的可以聊聊并查集在 Kruskal 最小生成树算法里的应用或者带权并查集但这两道题用不到所以点到为止即可。我个人刷到这两道题时的感受是108题很好写但109题第一次做很容易掉进“直接找环”的陷阱。因为你看到有向图第一反应是用拓扑排序或者DFS判环但拓扑排序只能找出环不能直接给出要删哪条边。而入度冲突这个条件才是“多余边”问题的题眼。如果你正在刷“代码随想录”的图论部分建议把这两道题一起做先做无向图的再做有向图的对比一下思路的变化。后面遇到更多并查集题目时你会发现核心模板永远是同一个变来变去的只是怎么用union的返回值去处理具体问题。最后分享一个小技巧在本地调试时可以自己构造几个测试用例比如[[1,2],[1,3],[2,3]]和[[1,2],[2,3],[3,1],[4,2]]然后打印每次合并时parent的变化。这个习惯能让你快速定位是并查集写错了还是业务逻辑判断错了。算法题最怕的不是不会思路而是小错误查不出来。有了这些基础这两道题对你来说就只是背模板、套逻辑的事了。