省份数量 图解题解
这道题到底在问什么
- 输入
- 6 城，相连：(0,1)(1,2)(0,2)(3,4)(4,5)(3,5)
- 输出
- 2（{0,1,2} 与 {3,4,5}）
最优解：一步一步想明白
- 3记住这套「各找老大 → 老大不同就合并、省份减一 → 老大相同就跳过」，下面每条相连关系都在套它。
- 4count = 6开局：6 个城市各自为省，每个城市的老大都是自己（没有箭头）。省份数从 6 起步，接下来按相连关系一对对合并。
- 5检查 (0,1)相连关系 (0, 1)：城市 0 和 1 直接相连，先各自往上找老大（根）。
- 6find(0)=0, find(1)=1顺着父指针往上爬：0 的根是 0，1 的根是 1。两者根不同。比的是根、不是直接父亲。
- 7union(0,1)；count=50 的老大是 0、1 的老大是 1，不同根 → 合并！把根 0 挂到根 1 下面，两省并成一省，省份数减一变成 5。
- 8检查 (1,2)相连关系 (1, 2)：城市 1 和 2 直接相连，先各自往上找老大（根）。
- 9find(1)=1, find(2)=2顺着父指针往上爬：1 的根是 1，2 的根是 2。两者根不同。比的是根、不是直接父亲。
- 10union(1,2)；count=41 的老大是 1、2 的老大是 2，不同根 → 合并！把根 1 挂到根 2 下面，两省并成一省，省份数减一变成 4。
- 11检查 (0,2)相连关系 (0, 2)：城市 0 和 2 直接相连，先各自往上找老大（根）。
- 12find(0)=2, find(2)=2顺着父指针往上爬：0 的根是 2，2 的根是 2。两者同根。比的是根、不是直接父亲。
- 130,2 同根 2，跳过0 和 2 的老大都是 2，已经同省了，无需合并，直接跳过。省份数不变，还是 4。
- 14检查 (3,4)相连关系 (3, 4)：城市 3 和 4 直接相连，先各自往上找老大（根）。
- 15find(3)=3, find(4)=4顺着父指针往上爬：3 的根是 3，4 的根是 4。两者根不同。比的是根、不是直接父亲。
- 16union(3,4)；count=33 的老大是 3、4 的老大是 4，不同根 → 合并！把根 3 挂到根 4 下面，两省并成一省，省份数减一变成 3。
- 17检查 (4,5)相连关系 (4, 5)：城市 4 和 5 直接相连，先各自往上找老大（根）。
- 18find(4)=4, find(5)=5顺着父指针往上爬：4 的根是 4，5 的根是 5。两者根不同。比的是根、不是直接父亲。
- 19union(4,5)；count=24 的老大是 4、5 的老大是 5，不同根 → 合并！把根 4 挂到根 5 下面，两省并成一省，省份数减一变成 2。
- 20检查 (3,5)相连关系 (3, 5)：城市 3 和 5 直接相连，先各自往上找老大（根）。
- 21find(3)=5, find(5)=5顺着父指针往上爬：3 的根是 5，5 的根是 5。两者同根。比的是根、不是直接父亲。
- 223,5 同根 5，跳过3 和 5 的老大都是 5，已经同省了，无需合并，直接跳过。省份数不变，还是 2。
- 23省份数 = 2所有相连关系处理完，城市归并成 2 棵树（2 个不同的根）——也就是 2 个省。同色的城市同属一省。这就是并查集数连通块的全部威力。
⚠️ 容易写错的地方
✗ 错：直接比 parent[i]==parent[j]
✓ 对：必须比 find(i)==find(j)
父指针只是上一级，不是根；要顺着一路找到根才能判断是否同省
✗ 错：合并时把城市挂城市
✓ 对：合并的是两个「根」
parent[i]=j 只接了一条，会割裂原来 i 那棵树；要 parent[find(i)]=find(j)
✗ 错：每对都 count-- 不判根
✓ 对：只有「根不同」才 count--
已同省的相连关系再减就会把省份数越减越少、算错
完整代码（Python / Java / C++）
Python
def findCircleNum(isConnected):
n = len(isConnected)
parent = list(range(n)) # 每个城市老大=自己
count = n
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # 路径压缩
x = parent[x]
return x
for i in range(n):
for j in range(i+1, n):
if isConnected[i][j]:
ri, rj = find(i), find(j)
if ri != rj:
parent[ri] = rj # 合并
count -= 1 # 省份减一
return countJava
int[] parent;
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length, count = n;
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (isConnected[i][j] == 1) {
int ri = find(i), rj = find(j);
if (ri != rj) { parent[ri] = rj; count--; } // 合并+减一
}
return count;
}
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}C++
vector<int> parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size(), count = n;
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (isConnected[i][j]) {
int ri = find(i), rj = find(j);
if (ri != rj) { parent[ri] = rj; count--; } // 合并+减一
}
return count;
}复杂度
时间
O(n²·α)
扫 n² 的矩阵，每次 find/union 近似 O(1)（α 反阿克曼）
空间
O(n)
只用一个长度 n 的 parent 数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 省份数量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
并查集的两个优化是什么？+
路径压缩（find 时把节点直接挂到根，树变扁）和按秩/按大小合并（把矮树挂到高树下，避免退化成链）。两者结合后单次操作近似 O(α(n))，几乎是常数。
这题能用 DFS/BFS 做吗？+
能。把矩阵看成图，对每个没访问过的城市做一次 DFS/BFS 染色，染色次数就是省份数。时间也是 O(n²)；并查集胜在「动态加边」场景（边一条条来）也能实时维护连通块。
什么时候首选并查集？+
需要频繁「合并集合 + 查询是否连通」、尤其边动态到来时（如冗余连接 LC684、账户合并 LC721）。静态一次性连通块用 DFS 也行。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 省份数量 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。