LeetCode 323中等图
无向图中连通分量的数目 图解题解
这道题到底在问什么
给 n 个点和无向边，数有多少个连通分量。
- 示例
- n=5, edges=[[0,1],[1,2],[3,4]] → 2
最优解：一步一步想明白
- 3每次查询连通性都 DFS 会重复。
- 4并查集开始每点一组，读到一条边就 union；最后根的数量就是分量数。
- 5连通分量 ＝ 几片互不相连的点群。并查集：初始每点独立(count=5)，每条边若连起两片就 count−1。
- 6find(0)=0、find(1)=1，两端不同片 → 合并成 {0,1}。分量数 5→4。
- 71 的根是 0、2 的根是 2，不同片 → 合并，{0,1,2} 连成一片。分量数 4→3。
- 83 与 4 不同片 → 合并成 {3,4}。分量数 3→2。
- 9边全部处理完，剩两片：{0,1,2} 和 {3,4}，互不相连 → 连通分量数 ＝ 2。
- 12一句话记住：并查集开始每点一组，读到一条边就 union；最后根的数量就是分量数。
- 15反例：若再加一条 (0,2)，find(0)=find(2)=0 已是同一片 → 这条边不产生新合并，count 不变。关键：只有「两端原本不同根」才 count−1。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“冗余边为什么不减少分量数”。
⚠️ 容易写错的地方
✗ 错：count 不初始化为 n
✓ 对：count 初始 ＝ n（每点一片）
连通分量从「全部独立」开始数，每成功合并一次减一。
✗ 错：合并前不判根，无脑 count−1
✓ 对：仅当两端不同根时才合并且 count−1
两端已同片的边是冗余边，不减少分量数。
✗ 错：忘了路径压缩，find 退化成链
✓ 对：find 加路径压缩
否则最坏每次 O(n)，整体退化。
完整代码（Python / C++ / Java）
Python
class Solution:
def countComponents(self, n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
count = n
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
count -= 1
return countC++
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x){ return p[x] == x ? x : p[x] = find(p[x]); };
int count = n;
for (auto& e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a != b) { p[b] = a; count--; }
}
return count;
}
};Java
class Solution {
public int countComponents(int n, int[][] edges) {
int[] p = new int[n];
for (int i=0;i<n;i++) p[i]=i;
int count = n;
for (int[] e: edges) {
int a = find(p,e[0]), b = find(p,e[1]);
if (a != b) { p[b] = a; count--; }
}
return count;
}
private int find(int[] p, int x) {
if (p[x] != x) p[x] = find(p, p[x]);
return p[x];
}
}套路模板 · 并查集数连通分量骨架
# 并查集数连通分量 骨架
parent = list(range(n)); count = n
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # 路径压缩
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb: # 两端不同片才合并
parent[rb] = ra
count -= 1
return count复杂度
时间复杂度
O((n+e)·α(n))
初始化 n + 每条边一次近 O(1) 的 union
空间复杂度
O(n)
仅 parent 数组存 n 个点
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 无向图中连通分量的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
并查集：parent 初始化为自身、count=n。逐条处理边，find 两端根，根不同则合并并 count−1，根相同则跳过。所有边处理完，count 即连通分量数。
这道题为什么用「图」，换最直接的暴力解会差在哪？+
图抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。