LeetCode 547. 省份数量
目录
题目描述
题意分析
输入是一个
n × n的矩阵isConnected，isConnected[i][j] == 1表示第i座城市和第j座城市之间有直达通路。题目定义「省份」是一组彼此直接或间接相连的城市，要求返回省份的总数。关键在于「间接」两个字：如果城市 0 与 1 相连、城市 1 与 2 相连，即使 0 和 2 之间没有直达通路，三者也属于同一个省份。所以这不是数矩阵里有多少个 1，而是把城市按「能不能互相到达」这种等价关系分组，然后数分组的个数。
输入形式也给了明确信号：矩阵是对称的（
isConnected[i][j] == isConnected[j][i]），对角线恒为 1（每座城市与自己相连）。对称意味着只需要扫描上三角就能覆盖所有城市对，扫描下三角只是把每对重复处理一遍；对角线恒为 1 则是无意义的自环，处理与否都不影响答案，但会影响某些写法的计数。数据范围是 $1 \le n \le 200$，矩阵最多四万个元素，所以读一遍矩阵的 $O(n^2)$ 开销是躲不掉的下界。
边界情况包括：只有一座城市时答案是 1；矩阵除对角线外全为 0 时答案是
n；矩阵全为 1 时答案是 1。
解法：并查集合并城市
核心思路
把城市看成点、直连关系看成无向边，「省份数量」就是图中连通分量的个数。邻接矩阵已经给出了所有城市对，因此无论 DFS、BFS 还是并查集，都至少要扫描 $O(n^2)$ 个矩阵元素。
并查集适合表达「两座城市是否属于同一连通块」：
parent[x]指向节点x所在集合的父节点，根节点是集合代表；find(x)找到代表元，并用路径压缩缩短后续查询；union(x, y)只在两个代表元不同时合并，按秩让矮树挂到高树下。核心不变量是：并查集中的每棵树对应一个当前已知的连通分量，
count等于树的棵数。 初始每座城市各自成树，所以count = n；每次成功合并两棵不同的树，连通分量恰好减少一个。若两点已经同根，这条边只是冗余边，不能再次减计数。矩阵关于主对角线对称，只扫描
j > i的上三角即可：既不会漏边，也跳过了无意义的自环和重复边。扫描结束后，所有直连关系都已完成合并，count就是答案。
解题步骤
- 初始化
parent[i] = i、rank[i] = 0，令count = n。- 枚举上三角中的城市对
(i, j)，即0 <= i < j < n。- 若
isConnected[i][j] == 1，分别找到两座城市的根。- 两根相同则跳过；两根不同则按秩合并，并执行
count--。- 扫描完矩阵后返回
count。例如
[[1,1,0],[1,1,1],[0,1,1]]：初始有 3 个集合；边(0,1)合并后剩 2 个，边(1,2)再合并后剩 1 个。虽然(0,2)没有直连边，但两者经城市 1 间接连通，因此答案是 1。
代码实现
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
UnionFind uf = new UnionFind(n);
int count = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1 && uf.union(i, j)) {
count--;
}
}
}
return count;
}
private static class UnionFind {
private final int[] parent;
private final int[] rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return false;
}
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
}
func findCircleNum(isConnected [][]int) int {
n := len(isConnected)
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
count := n
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if isConnected[i][j] == 1 && unionProvince(parent, rank, i, j) {
count--
}
}
}
return count
}
func findProvince(parent []int, x int) int {
if parent[x] != x {
parent[x] = findProvince(parent, parent[x])
}
return parent[x]
}
func unionProvince(parent, rank []int, x, y int) bool {
rootX := findProvince(parent, x)
rootY := findProvince(parent, y)
if rootX == rootY {
return false
}
if rank[rootX] < rank[rootY] {
parent[rootX] = rootY
} else if rank[rootX] > rank[rootY] {
parent[rootY] = rootX
} else {
parent[rootY] = rootX
rank[rootX]++
}
return true
}
复杂度分析
- 时间复杂度：$O(n^2 \alpha(n))$。矩阵上三角有 $O(n^2)$ 个元素，每次并查集操作的摊还复杂度为 $\alpha(n)$；在实际数据范围内可近似看作 $O(n^2)$。
- 空间复杂度：$O(n)$。
parent和rank数组各保存 $n$ 个元素。
关键点总结
- 先把题目抽象成「统计无向图的连通分量」，再选择 DFS、BFS 或并查集。
count从n开始，只有union合并了两个不同集合时才减一。- 对称矩阵只需扫描上三角；对角线的自环不影响连通性。
- 路径压缩负责缩短查询路径，按秩合并负责避免树退化，两者共同保证近常数的摊还操作。
- 若图一次性给出，DFS/BFS 代码通常更短；若边动态加入并需持续查询连通性，并查集更合适。
易错点总结
- 看到一个
1就无条件count--：全连通的 3 个点有 3 条边，但只有两次有效合并，第三条是冗余边。- 忽略间接连通：
0-1-2即使没有边0-2，仍然只有一个省份。union直接连接原节点而不是两个根，会破坏集合关系；必须先调用find。- 用
parent数组中的不同值数量作为答案不可靠，因为部分节点可能仍指向中间节点；本实现直接维护连通块计数。- 统计上三角时内层应从
i + 1开始；从 0 开始虽不一定算错，却会重复处理每条无向边。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 323. 无向图中连通分量的数目 | 中等 | 边表输入下的连通分量计数 |
| 684. 冗余连接 | 中等 | 用合并失败定位成环的多余边 |
| 721. 账户合并 | 中等 | 字符串映射到下标后再合并 |
| 765. 情侣牵手 | 困难 | 交换次数等于点数减连通块数 |
| 839. 相似字符串组 | 困难 | 两两判定相似后再建边合并 |
| 990. 等式方程的可满足性 | 中等 | 先并等式再用不等式查矛盾 |
| 1202. 交换字符串中的元素 | 中等 | 连通分量内部自由排序 |
| LCR 116. 省份数量 | 中等 | 本题的同题异名版本 |
| LCR 117. 相似字符串组 | 困难 | 839 题的同题异名版本 |
| LCR 118. 冗余连接 | 中等 | 684 题的同题异名版本 |
| 面试题 17.07. 婴儿名字 | 中等 | 按字典序指定集合的代表元 |