LeetCode 684中等并查集
冗余连接 图解题解
这道题到底在问什么
给一棵树多加一条边，找出造成环的那条边。
- edges
- [[1,2],[1,3],[2,3]]
- 输出
- [2,3]
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合并查集。
- 4edges=[[1,2],[1,3],[2,3]]。开始时 1、2、3 各成一块（三种颜色），parent 都指向自己。
- 5find(1)=1、find(2)=2 不同根：合并，让 2 指向 1。1、2 变同色，连通块 3→2。
- 6find(1)=1、find(3)=3 不同根：合并，3 也指向 1。现在 1、2、3 全同色（同一根 1）。
- 7轮到 [2,3]：find(2) 顺着 2→1 得根 1，find(3) 顺着 3→1 也得根 1 —— 两端同根。
- 82、3 早已在同一块里（同色）。再把 2-3 直接连上，1-2-3 就闭合成环 —— 这正是多出来的那条边。
- 9并查集发现某条边的两端已经同根，这条边就是多余的那条。
- 10题目保证恰有一条多余边；遍历时遇到的第一条同根边就是要返回的答案。
- 11返回 [2,3]。
- 14把这句话记住，下次遇到同类题，就能更快选出方向。
⚠️ 容易写错的地方
✗ 错：看到重复节点就认为是环
✓ 对：必须判断两个端点是否同根
节点出现多次不等于成环
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def findRedundantConnection(self, edges):
parent = {}
def find(x):
parent.setdefault(x, x)
if parent[x] != x:
parent[x] = find(parent[x]) # 路径压缩
return parent[x]
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb: # 两端已同根 → 冗余边
return [a, b]
parent[rb] = ra # 后一个点的根挂到前一个
return []C++
class Solution {
public:
vector<int> par;
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
par.resize(n + 1);
for (int i = 0; i <= n; i++) par[i] = i;
for (auto& e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra == rb) return e; // 两端已同根 → 冗余边
par[rb] = ra; // 后者的根挂到前者
}
return {};
}
};Java
class Solution {
int[] par;
int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); }
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
par = new int[n + 1];
for (int i = 0; i <= n; i++) par[i] = i;
for (int[] e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra == rb) return e; // 两端已同根 → 冗余边
par[rb] = ra; // 后者的根挂到前者
}
return new int[0];
}
}套路模板 · 并查集
# 并查集 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界复杂度
时间复杂度
O(n α(n))
n 条边各做一次 union；带路径压缩后单次几乎 O(1)，整体接近线性的反阿克曼 α(n)
空间复杂度
O(n)
只用一个 parent 数组记录每个点的父亲
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 冗余连接 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用并查集而不是 DFS 找环？+
并查集逐边在线判断两端是否已连通，遇第一条成环的边即答案，O(n·α)；DFS 找环实现更繁。
并查集的两个优化？+
路径压缩(find 时挂到根)+ 按秩合并，近乎 O(1) 每次。
有多条多余边的变体？+
本题保证一条；多条要按特定条件挑那条。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。