题目描述
城市之间有的相连。直接或间接相连的城市属于同一个省，求省份总数。
关系 = 0—1 相连，1—2 相连，3 独立
输出 = 2
思路解析
每个城市记一个「老大(根)」。查 = 顺着 parent 找到根；并 = 把一个城市的根挂到另一个的根下。根的个数 = 省份数。
初始：各自为政：一开始每个城市自成一省，自己是自己的老大(颜色各不同)，省份数 = 4。
用 parent 数组记每个城市的老大。一开始 parent[i]=i，人人是自己的老大，共 4 个不同的根 = 4 个省。
0 — 1 相连：城市 0、1 相连：把 1 的老大设成 0。现在 0、1 同色(同一省)，省份数减到 3。
1 — 2 相连：城市 1、2 相连：1 的老大是 0，于是把 2 也挂到 0 下面。0、1、2 连成一片，省份数 = 2。
再连已同组的：若再遇到「0 和 2 相连」：一查它俩老大都是 0，已经同省，省份数不变。这是并查集自动去重的关键。
结果：处理完所有关系：{0,1,2} 一个省、{3} 一个省，共 2 个省。
最后遍历所有城市求各自的根：find(0)=find(1)=find(2)=0、find(3)=3，共 2 个不同的根 → 2 个省。
凡是「动态地把元素并组、问有几组/是否连通」，并查集最快：朋友圈、连通网络、冗余连接都用它。
参考代码（Python）
Python
1parent = list(range(n)) # 一开始各自为根
2def find(x): # 查：找老大
3 while parent[x] != x: x = parent[x]
4 return x
5def union(a, b): # 并：认同一个老大
6 parent[find(a)] = find(b)
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 把根挂根、数不同根 = 组数。朋友圈、冗余连接、等式方程全是它。
Python
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(a)] = find(b) # 并的是class="cl-str">"根"
9# 合并所有关系后: len({find(i) for i in range(n)}) = 组数易错点
- ❌ union 写成 parent[a]=b → ✅ parent[find(a)] = find(b)（要挂的是「根」，不是节点本身）
- ❌ 数省份时漏更新计数 → ✅ 最后统计不同 find(i) 的个数最稳（避免合并时漏减）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。