题目描述
思路解析动画文字版
0—1、1—2 相连，那 0 和 2 也算间接相连同一省。如果手动 DFS/标记，关系一多就容易漏掉间接连通或重复数。并查集专治这种「动态合并 + 数有几组」。
转折：每个城市记一个「老大(根)」parent[i]。find = 顺着 parent 一路找到根；union(a,b) = 把 a 的根挂到 b 的根下。相连就 union 一下，最后不同根的个数 = 省份数。间接相连会自动并进同一个根，去重也免费。
初始 · 各自为政：开局每个城市自成一省，parent[i]=i，自己是自己的老大（颜色各不同），count = 4。关系：0—1、1—2、0—2（冗余）、3 独立。
关系 0—1 · find 两个根：处理 0—1：先各自 find 根。find(0)=0、find(1)=1，根不同，说明还没合并，可以并。
关系 0—1 · union 挂根：把 1 的根挂到 0 下：parent[1]=0。0、1 同色成一组，count 减到 3。
关系 1—2 · find 两个根：处理 1—2：find(1) 顺着 parent 走到根 0，find(2)=2，根不同，可以并。
关系 1—2 · union 挂根：把 2 的根（2）挂到 1 的根（0）下：parent[2]=0。0、1、2 连成一片，count = 2。注意 union 挂的是根，不是节点本身。
关系 0—2 · 已同根（负例，不合并）：再遇到冗余关系 0—2：find(0)=0、find(2)=0，根相同，它俩早已同省。什么都不做，count 不变——这就是并查集自动去重的关键负例。
城市 3 · 始终独立：城市 3 没出现在任何关系里，没人和它 union，它的根一直是自己：find(3)=3，自成一省。
数根 → 结果：遍历每个城市求根：find(0)=find(1)=find(2)=0、find(3)=3，共 2 个不同的根 → 2 个省（{0,1,2} 和 {3}）。
凡是「动态地把元素并组、问有几组/是否连通」，并查集最快：朋友圈、连通网络、冗余连接都用它。
参考代码
class Solution: def findCircleNum(self, isConnected): n = len(isConnected) parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra != rb: parent[rb] = ra for i in range(n): for j in range(i + 1, n): if isConnected[i][j] == 1: union(i, j) return len({find(i) for i in range(n)})复杂度
- 时间复杂度：≈ O(n²)，遍历关系矩阵
- 空间复杂度：O(n)，parent 数组
可套用的代码模板
记住骨架：parent 数组、find 顺藤找根、union 把根挂根、数不同根 = 组数。朋友圈、冗余连接、等式方程全是它。
Python
# 「动态合并、问几组 / 是否连通」都套parent = list(range(n))def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # 路径压缩(可选) x = parent[x] return xdef union(a, b): parent[find(b)] = find(a) # 并的是"根"# 合并所有关系后: len({find(i) for i in range(n)}) = 组数易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
冗余连接
LeetCode 684 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题