题目描述
思路解析动画文字版
每次查询连通性都 DFS 会重复。
并查集开始每点一组，读到一条边就 union；最后根的数量就是分量数。
① 初始：每个点自成一片，count = n = 5：连通分量 ＝ 几片互不相连的点群。并查集：初始每点独立(count=5)，每条边若连起两片就 count−1。
② 合并 (0,1)：根不同 → 合并，count 5→4：find(0)=0、find(1)=1，两端不同片 → 合并成 {0,1}。分量数 5→4。
③ 合并 (1,2)：find(1)=0、find(2)=2 不同 → 合并，4→3：1 的根是 0、2 的根是 2，不同片 → 合并，{0,1,2} 连成一片。分量数 4→3。
④ 合并 (3,4)：根不同 → 合并，3→2：3 与 4 不同片 → 合并成 {3,4}。分量数 3→2。
⑤ 所有边处理完：剩 {0,1,2} 与 {3,4} → 答案 2：边全部处理完，剩两片：{0,1,2} 和 {3,4}，互不相连 → 连通分量数 ＝ 2。
一句话记住：并查集开始每点一组，读到一条边就 union；最后根的数量就是分量数。
边界三连：本题真边界：无边、全连通、重复边。
⑥ 冗余边不减 count：两端已同根则跳过：反例：若再加一条 (0,2)，find(0)=find(2)=0 已是同一片 → 这条边不产生新合并，count 不变。关键：只有「两端原本不同根」才 count−1。
面试追问 · 核心思路：思路：并查集，count 从 n 开始，成功 union 一次减一。
面试追问 · 并查集 vs DFS/BFS：DFS/BFS 也能求；并查集擅长动态加边。
面试追问 · 复杂度：复杂度：并查集 O((n+e)·α(n))≈O(n+e)。
这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“冗余边为什么不减少分量数”。
参考代码
class Solution: def countComponents(self, n, edges): parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x count = n for a, b in edges: ra, rb = find(a), find(b) if ra != rb: parent[rb] = ra count -= 1 return count复杂度
- 时间复杂度：O((n+e)·α(n))，初始化 n + 每条边一次近 O(1) 的 union
- 空间复杂度：O(n)，仅 parent 数组存 n 个点
可套用的代码模板
记牢：count=n 起步 → 逐边 find 两端 → 不同根才合并并 count−1 → 返回 count。
Python
# 并查集数连通分量 骨架parent = list(range(n)); count = ndef find(x): while parent[x] != x: parent[x] = parent[parent[x]] # 路径压缩 x = parent[x] return xfor a, b in edges: ra, rb = find(a), find(b) if ra != rb: # 两端不同片才合并 parent[rb] = ra count -= 1return count易错点
面试追问把动画讲成自己的话
追问整体思路是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
以图判树
LeetCode 261 · 中等 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题