LeetCode 323. 无向图中连通分量的数目
目录
题目描述
题意分析
给定
n个编号为0到n-1的节点，以及一个无向边列表edges，求这张图有多少个连通分量。连通分量指的是极大的「互相可达」的节点集合——集合内任意两点之间存在路径，且再加入任何一个外部节点都会破坏这个性质。注意题目只问数量，不问每个分量里有哪些点，也不问分量大小。这个「只要计数」的要求很关键：它意味着我们不需要真的把分量枚举出来，只要能维护一个计数器就够了。
图是无向的，所以边没有方向，
[0,1]和[1,0]等价；节点编号连续且从 0 开始，天然适合用数组下标而不是哈希表存储辅助信息。孤立点（不出现在任何边里的节点）本身就是一个连通分量，绝不能因为它没有边就被忽略。「若干次合并 + 询问集合个数」这个形态，是并查集的典型信号。当然 DFS 或 BFS 也能做——建邻接表后对每个未访问节点起一次搜索，起搜次数就是分量数——但那需要先花 $O(n + m)$ 建图，而并查集连图都不用建，直接在边列表上流式处理即可。题目若进一步演化成「边是逐条到来的，每加一条边就问一次分量数」，DFS 方案要整体重算而并查集能增量维护，这也是面试更期待并查集的原因。
边界：
edges为空时答案就是n（每个点各自成块）；n = 0时答案是 0；输入可能含重复边（同一对节点出现多次），必须保证重复边不会把计数减两次；本题保证无自环，但健壮的实现遇到自环（u == v）也应当不改变计数。
解法：并查集计数连通块
核心思路
每个节点初始都是一个连通分量，数量为
n。逐条加入无向边时，若两个端点属于不同集合，合并后分量数减少 1；若已经同属一个集合，这条边不改变连通性。并查集正好支持这两个操作：
find(x)找到节点所属集合的根，union(a,b)在根不同时合并。路径压缩缩短后续查找，按大小合并避免小树成为大树的父节点。不变量：处理完任意边前缀后，并查集中的集合与该前缀形成的连通分量一一对应，
components等于集合数量。 初始没有边时成立；一条边在同一集合内不会改变分量，跨集合边恰好把两个分量合成一个，因此不变量持续成立。正确性说明：全部边处理完后，
components就是原图的连通分量数。孤立点从未被合并，仍作为单独集合自然计入。
解题步骤
- 初始化
parent[i]=i、size[i]=1和components=n。- 对每条边找到两个端点的根。
- 根相同则跳过；否则把较小集合挂到较大集合下，并令
components--。- 返回
components。
n=5、边为[[0,1],[1,2],[3,4]]时，三次有效合并使分量数从 5 降到 2。若再加入[0,2]，两个端点已经同根，计数不能再次减少。空边集则直接返回n。
代码实现
class Solution {
public int countComponents(int n, int[][] edges) {
int[] parent = new int[n];
int[] size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
int components = n;
for (int[] edge : edges) {
int rootA = find(parent, edge[0]);
int rootB = find(parent, edge[1]);
if (rootA == rootB) {
continue;
}
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
components--;
}
return components;
}
private int find(int[] parent, int node) {
while (node != parent[node]) {
parent[node] = parent[parent[node]];
node = parent[node];
}
return node;
}
}
func countComponents(n int, edges [][]int) int {
parent := make([]int, n)
size := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
size[i] = 1
}
find := func(node int) int {
for node != parent[node] {
parent[node] = parent[parent[node]]
node = parent[node]
}
return node
}
components := n
for _, edge := range edges {
rootA := find(edge[0])
rootB := find(edge[1])
if rootA == rootB {
continue
}
if size[rootA] < size[rootB] {
rootA, rootB = rootB, rootA
}
parent[rootB] = rootA
size[rootA] += size[rootB]
components--
}
return components
}
复杂度分析
设节点数为
n、边数为m。
- 时间复杂度： $O(n+m\alpha(n))$，其中 $\alpha$ 是反阿克曼函数。
- 空间复杂度： $O(n)$。
关键点总结
- 只关心动态合并后的连通性与集合数时，并查集比显式建邻接表更直接。
- 分量数从
n开始，只在两个不同根成功合并时减一。- 路径压缩不改变集合归属，按大小合并控制树高。
- 冗余边、自环和重复边都不会改变分量数。
易错点总结
- 每条边都令计数减一： 环内边和重复边并不会合并两个分量。
- 直接比较
parent[a]与parent[b]： 父节点未必是根，必须调用find。- 忘记初始化
parent[i]=i： 默认零值会把节点错误地视为同组。- 合并后更新了非根节点的
size： 后续按大小选择会失真。- 漏算孤立点： 从
components=n开始即可自然包含它们。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 547. 省份数量 | 中等 | 输入是邻接矩阵而非边列表，要先把矩阵上三角转成合并操作，其余与本题相同 |
| 684. 冗余连接 | 中等 | 利用 union 返回 false 的时刻定位成环的那条边，是本题返回值设计的直接应用 |
| 721. 账户合并 | 中等 | 元素是字符串需先映射成整数下标，合并后还要按根收集并排序输出各集合内容 |
| 765. 情侣牵手 | 困难 | 答案是「节点数减分量数」，考察把最少交换次数转化为分量计数的建模 |
| 839. 相似字符串组 | 困难 | 边不是给定的而要 $O(n^2)$ 两两判定相似性再合并，考察隐式图上的并查集 |
| 990. 等式方程的可满足性 | 中等 | 分两趟：先处理全部等式建集合，再用不等式检验冲突，考察操作顺序的必要性 |
| 1202. 交换字符串中的元素 | 中等 | 合并出可交换下标组后在组内排序，考察并查集结果的二次利用 |
| LCR 116. 省份数量 | 中等 | 与 547 同题，可直接套用本题模板 |
| LCR 117. 相似字符串组 | 困难 | 与 839 同题，重点仍在相似判定的剪枝 |
| LCR 118. 冗余连接 | 中等 | 与 684 同题，练习成环时刻的捕捉 |
| 面试题 17.07. 婴儿名字 | 中等 | 合并时需要按字典序选定代表元并累加频次，考察带附加信息的并查集 |