省份数量
Number of Provinces
本机进度仅保存在当前浏览器
题目描述
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。「省份」是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，返回矩阵中省份的数量。
示例：isConnected = [[1,1,0],[1,1,0],[0,0,1]]，输出 2。
解题思路
- 省份即无向图的连通分量，并查集（Union-Find）是这类"动态合并集合 + 查询代表元"问题的标配结构。
- 初始化每个城市自成一个集合；遍历邻接矩阵，相连的城市执行 union 合并。
- 合并时按秩/大小连接并在查找时路径压缩，均摊复杂度近似 O(1)；最终省份个数 = 独立集合数（可由合并成功次数倒数得到）。
- DFS/BFS 求连通分量同样可行，本题数据形态（邻接矩阵）与并查集特别契合。
参考实现
查看参考实现Python · 建议先自行作答
def findCircleNum(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
provinces = n
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
provinces -= 1
return provinces