企业官网建设流程全解析

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 解题思路：如何用并查集检测环

思路很简单：

1. 初始化一个大小为 n+1 的并查集。
2. 遍历edges中的每条边[u, v]。
3. 调用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 两种冲突情况的分类讨论

我们先枚举所有可能：

1. 没有节点入度为2，但图中有环。这时多余的边就是构成环的那条边，直接用并查集遍历，第一次导致环的边就是答案。
2. 有一个节点入度为2。这时有两条候选边都指向该节点。我们需要删除其中一条。判断标准是：删除哪条边之后，剩余的图能成为一棵有向树？
   • 如果删除候选边1后，剩余图中没有环，那么候选边1就是答案。
   • 如果删除候选边1后，剩余图中仍有环，那么答案就是候选边2。
   • 还有一种特殊情况：两条候选边里有一条本身就在环上，另一条不在，那删除在环上的那条即可。

这里有一个容易搞混的点：入度为2的节点，它的两条候选边可能一条是“真正的多余边”，另一条是“原树里正常的边”。你要删除的是多余的那条。怎么判断呢？最简单的办法是：先假设删除第一条候选边（比如输入中位置靠前的），然后用并查集检查剩余图是否合法。如果合法，删除第一条；如果不合法，说明第一条是必要的，只能删除第二条。

但这样直接做有个坑：题目要求“返回最后出现的多余边”，如果两种删除方案都可行呢？实际上在有向树中，如果入度冲突和环同时存在，只有一种删除方案能让图变成树。如果不存在入度冲突只有环，那么只有一条构成环的边是多余的。所以不会出现二义性。

4.3 解题步骤：先处理入度为2，再处理环

我推荐的解题流程：

1. 先记录所有节点的入度。
2. 找到入度为2的节点，记为node，它的两条入边分别记为候选candidate1和candidate2（按输入顺序，candidate1在前，candidate2在后）。
3. 先尝试删除candidate1，用并查集检查剩下的边是否能构成一棵有向树（无环）。
   • 如果可行，答案就是candidate1。
   • 如果不可行，答案就是candidate2。
4. 如果不存在入度为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. 从刷题到面试：这类题怎么讲清楚

很多读者问：我刷了题，但面试时怎么才能让面试官觉得我厉害？对于并查集，建议按这个顺序讲：

1. 先说清楚问题：给一个树多加一条边，找多余边。
2. 说明为什么想到并查集：因为需要判断“两个点是否已经连通”。
3. 解释并查集的两种优化：路径压缩和按秩合并。
4. 无向图场景直接套模板。
5. 有向图场景先找入度为2的节点，再尝试删除候选边，最后检查环。

如果你能直接在白板上写出上面两段代码，并说明每一行在做什么，面试官一般不会刁难你。更进阶的可以聊聊并查集在 Kruskal 最小生成树算法里的应用，或者带权并查集，但这两道题用不到，所以点到为止即可。

我个人刷到这两道题时的感受是：108题很好写，但109题第一次做很容易掉进“直接找环”的陷阱。因为你看到有向图，第一反应是用拓扑排序或者DFS判环，但拓扑排序只能找出环，不能直接给出要删哪条边。而入度冲突这个条件，才是“多余边”问题的题眼。

如果你正在刷“代码随想录”的图论部分，建议把这两道题一起做，先做无向图的，再做有向图的，对比一下思路的变化。后面遇到更多并查集题目时，你会发现核心模板永远是同一个，变来变去的只是怎么用union的返回值去处理具体问题。

最后分享一个小技巧：在本地调试时，可以自己构造几个测试用例，比如[[1,2],[1,3],[2,3]]和[[1,2],[2,3],[3,1],[4,2]]，然后打印每次合并时parent的变化。这个习惯能让你快速定位是并查集写错了，还是业务逻辑判断错了。算法题最怕的不是不会思路，而是小错误查不出来。有了这些基础，这两道题对你来说就只是背模板、套逻辑的事了。