题目描述
思路解析动画文字版
记住这一句，下面每条边都在套它。
起手：8 个节点，每个都是自己的根，连通分量数 = 8。下面逐条处理边，把两端并成一组。
看边 (0,1)：0 的根是 0，1 的根是 1，根不同 → 需要合并。
合并：让根 1 指向根 0，两组并成一组（同色）。连通分量数 -1 → 7。
看边 (1,2)：1 的根是 0，2 的根是 2，根不同 → 需要合并。
合并：让根 2 指向根 0，两组并成一组（同色）。连通分量数 -1 → 6。
看边 (5,6)：5 的根是 5，6 的根是 6，根不同 → 需要合并。
合并：让根 6 指向根 5，两组并成一组（同色）。连通分量数 -1 → 5。
看边 (2,3)：2 的根是 0，3 的根是 3，根不同 → 需要合并。
合并：让根 3 指向根 0，两组并成一组（同色）。连通分量数 -1 → 4。
看边 (0,4)：0 的根是 0，4 的根是 4，根不同 → 需要合并。
合并：让根 4 指向根 0，两组并成一组（同色）。连通分量数 -1 → 3。
看边 (1,3)：查根发现 1、3 的根都是 0，已经在同一组里。
同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
看边 (4,2)：查根发现 4、2 的根都是 0，已经在同一组里。
同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
看边 (6,5)：查根发现 6、5 的根都是 5，已经在同一组里。
同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
看边 (3,0)：查根发现 3、0 的根都是 0，已经在同一组里。
同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
所有边处理完，剩下 3 个根 → 一共 3 个连通分量（三种颜色）。这就是答案。
边界先想清。
两个高频追问。
参考代码
class Solution { int[] parent; public int countComponents(int n, int[][] edges) { parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; int count = n; for (int[] e : edges) { int ra = find(e[0]), rb = find(e[1]); if (ra != rb) { parent[rb] = ra; count--; } } return count; } int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }}复杂度
- 时间：O((n+m)·α)，m 条边，每次 find 近乎常数（路径压缩）
- 空间：O(n)，一个 parent 数组
易错点
面试追问把动画讲成自己的话
追问为什么用并查集而不是 DFS/BFS？
追问按秩合并有必要吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
以图判树
LeetCode 261 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题