题目描述
城市之间有的相连。直接或间接相连的城市属于同一个省，求省份总数。
思路解析
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}）。
凡是「动态地把元素并组、问有几组/是否连通」，并查集最快：朋友圈、连通网络、冗余连接都用它。
参考代码（Python）
1parent = list(range(n)) # 一开始各自为根
2def find(x): # 查：找老大
3 while parent[x] != x: x = parent[x]
4 return x
5def union(a, b): # 并：把 b 的根挂到 a 的根下
6 parent[find(b)] = find(a)
7for i in range(n):
8 for j in range(i+1, n):
9 if isConnected[i][j]: union(i, j)
10return len({find(i) for i in range(n)}) # 不同根的个数复杂度分析
- 时间复杂度：≈ O(n²) —— 遍历关系矩阵
- 空间复杂度：O(n) —— parent 数组
套路模板
记住骨架：parent 数组、find 顺藤找根、union 把根挂根、数不同根 = 组数。朋友圈、冗余连接、等式方程全是它。
1# 「动态合并、问几组 / 是否连通」都套
2parent = list(range(n))
3def find(x):
4 while parent[x] != x:
5 parent[x] = parent[parent[x]] # 路径压缩(可选)
6 x = parent[x]
7 return x
8def union(a, b): parent[find(b)] = find(a) # 并的是class="cl-str">"根"
9# 合并所有关系后: len({find(i) for i in range(n)}) = 组数易错点
- 错误写法：union 写成 parent[a]=b → 正确写法：parent[find(b)] = find(a)（要挂的是「根」，不是节点本身）
- 错误写法：数省份时漏更新计数 → 正确写法：最后统计不同 find(i) 的个数最稳（避免合并时漏减）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。