题目描述
思路解析动画文字版
记住这一句，下面每条边都在套它。
起手：11 个节点、11 条边。一棵 11 节点的树只该有 11-1=10 条边，这里多了一条——多出来的那条会让图里出现一个环，它就是要找的冗余边。下面逐条加边、揪出成环的那条。
看边 [1,2]：1 的根是 1，2 的根是 2，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 2 指向根 1，两块并成一块（同色）。连通块数 -1 → 10。
看边 [1,3]：1 的根是 1，3 的根是 3，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 3 指向根 1，两块并成一块（同色）。连通块数 -1 → 9。
看边 [2,4]：2 的根是 1，4 的根是 4，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 4 指向根 1，两块并成一块（同色）。连通块数 -1 → 8。
看边 [2,5]：2 的根是 1，5 的根是 5，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 5 指向根 1，两块并成一块（同色）。连通块数 -1 → 7。
看边 [3,6]：3 的根是 1，6 的根是 6，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 6 指向根 1，两块并成一块（同色）。连通块数 -1 → 6。
看边 [3,7]：3 的根是 1，7 的根是 7，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 7 指向根 1，两块并成一块（同色）。连通块数 -1 → 5。
看边 [4,8]：4 的根是 1，8 的根是 8，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 8 指向根 1，两块并成一块（同色）。连通块数 -1 → 4。
看边 [5,9]：5 的根是 1，9 的根是 9，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 9 指向根 1，两块并成一块（同色）。连通块数 -1 → 3。
看边 [6,10]：6 的根是 1，10 的根是 10，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 10 指向根 1，两块并成一块（同色）。连通块数 -1 → 2。
看边 [7,11]：7 的根是 1，11 的根是 11，根不同 → 这条边接通了两个原本分开的块，安全合并、不成环。
合并：让根 11 指向根 1，两块并成一块（同色）。连通块数 -1 → 1。
看边 [5,2]：查根发现 5、2 的根都是 1，它俩在之前的边里早就连通了——再连这条边就把已连通的两点圈成了环。
两端已同根 → 加上这条边就成环！这条 [5,2] 就是多余的冗余边，正是答案。
结论：逐条加边时，第一条「两端已经连通」的边 [5,2] 就是冗余边——删掉它，剩下的 10 条边正好连成一棵无环的树（全连成一块、同色）。
边界先想清。
两个高频追问。
参考代码
class Solution { int[] parent; public int[] findRedundantConnection(int[][] edges) { int n = edges.length; parent = new int[n + 1]; for (int i = 1; i <= n; i++) parent[i] = i; for (int[] e : edges) { int ra = find(e[0]), rb = find(e[1]); if (ra == rb) return e; // 两端已同根 -> 成环 -> 冗余边 parent[rb] = ra; } return new int[0]; } int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }}复杂度
- 时间：O(n·α)，n 条边，每次 find 近乎常数（路径压缩）
- 空间：O(n)，一个 parent 数组
易错点
面试追问把动画讲成自己的话
追问为什么遇到第一条成环的边就能直接返回？
追问不用并查集还能怎么做？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
无向图中连通分量的数目
LeetCode 323 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题