§1

题目描述

给一棵树多加一条边，找出造成环的那条边。

edges = [[1,2],[1,3],[2,3]]

输出 = [2,3]

§2

思路解析动画文字版

关键不是背模板，而是看懂为什么这题适合并查集。

1. 三个点，各自独立：edges=[[1,2],[1,3],[2,3]]。开始时 1、2、3 各成一块（三种颜色），parent 都指向自己。

2. 连 [1,2]：不同根 → 合并：find(1)=1、find(2)=2 不同根：合并，让 2 指向 1。1、2 变同色，连通块 3→2。

3. 连 [1,3]：不同根 → 合并：find(1)=1、find(3)=3 不同根：合并，3 也指向 1。现在 1、2、3 全同色（同一根 1）。

4. 连 [2,3]：先查两端的根：轮到 [2,3]：find(2) 顺着 2→1 得根 1，find(3) 顺着 3→1 也得根 1 —— 两端同根。

5. 同根再连 = 形成环：2、3 早已在同一块里（同色）。再把 2-3 直接连上，1-2-3 就闭合成环 —— 这正是多出来的那条边。

6. 这条边就是冗余连接：并查集发现某条边的两端已经同根，这条边就是多余的那条。

7. 按输入顺序返回：题目保证恰有一条多余边；遍历时遇到的第一条同根边就是要返回的答案。

8. 答案 = [2,3]：返回 [2,3]。

把这句话记住，下次遇到同类题，就能更快选出方向。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。

§3

参考代码

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 []

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(n α(n))，n 条边各做一次 union；带路径压缩后单次几乎 O(1)，整体接近线性的反阿克曼 α(n)
空间复杂度：O(n)，只用一个 parent 数组记录每个点的父亲

§5

可套用的代码模板

模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。

Python

# 并查集 通用检查表# 1. 定义状态/指针/容器# 2. 每轮只做一个清晰动作# 3. 更新答案并处理边界

§6

易错点

✗ 错误写法：看到重复节点就认为是环

✓ 正确写法：必须判断两个端点是否同根

节点出现多次不等于成环

✗ 错误写法：只按样例推代码

✓ 正确写法：先写清状态含义和边界条件

样例太少，隐藏用例专打边界

✗ 错误写法：变量名和动画不一致

✓ 正确写法：代码变量沿用动画里的核心名字

学习时最怕脑内维护两套概念

面试追问把动画讲成自己的话

追问为什么用并查集而不是 DFS 找环？

并查集逐边在线判断两端是否已连通，遇第一条成环的边即答案，O(n·α)；DFS 找环实现更繁。

追问并查集的两个优化？

路径压缩(find 时挂到根)+ 按秩合并，近乎 O(1) 每次。

追问有多条多余边的变体？

本题保证一条；多条要按特定条件挑那条。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 图 11/15

无向图中连通分量的数目

LeetCode 323 · 中等 · 沿着图继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

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 []