LeetCode 323中等图
无向图中连通分量的数目 图解题解
这道题到底在问什么
有 n 个节点（0..n-1）和若干无向边 edges。互相能连通的节点算一组，求图中连通分量的个数。
- 输入
- n=8, edges=[[0,1],[1,2],[5,6],[2,3],[0,4],[1,3],[4,2],[6,5],[3,0]]
- 输出
- 3
最优解：一步一步想明白
- 3记住这一句，下面每条边都在套它。
- 4起手：8 个节点，每个都是自己的根，连通分量数 = 8。下面逐条处理边，把两端并成一组。
- 5看边 (0,1)：0 的根是 0，1 的根是 1，根不同 → 需要合并。
- 6合并：让根 1 指向根 0，两组并成一组（同色）。连通分量数 -1 → 7。
- 7看边 (1,2)：1 的根是 0，2 的根是 2，根不同 → 需要合并。
- 8合并：让根 2 指向根 0，两组并成一组（同色）。连通分量数 -1 → 6。
- 9看边 (5,6)：5 的根是 5，6 的根是 6，根不同 → 需要合并。
- 10合并：让根 6 指向根 5，两组并成一组（同色）。连通分量数 -1 → 5。
- 11看边 (2,3)：2 的根是 0，3 的根是 3，根不同 → 需要合并。
- 12合并：让根 3 指向根 0，两组并成一组（同色）。连通分量数 -1 → 4。
- 13看边 (0,4)：0 的根是 0，4 的根是 4，根不同 → 需要合并。
- 14合并：让根 4 指向根 0，两组并成一组（同色）。连通分量数 -1 → 3。
- 15看边 (1,3)：查根发现 1、3 的根都是 0，已经在同一组里。
- 16同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
- 17看边 (4,2)：查根发现 4、2 的根都是 0，已经在同一组里。
- 18同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
- 19看边 (6,5)：查根发现 6、5 的根都是 5，已经在同一组里。
- 20同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
- 21看边 (3,0)：查根发现 3、0 的根都是 0，已经在同一组里。
- 22同组无需合并，连通分量数不变，仍是 3。冗余边对答案没有影响。
- 23所有边处理完，剩下 3 个根 → 一共 3 个连通分量（三种颜色）。这就是答案。
⚠️ 容易写错的地方
✗ 错：把节点数当答案
✓ 对：答案是「剩下的根数」count，不是 n
每次成功合并 count 才减一
✗ 错：冗余边也减 count
✓ 对：两端已同根就跳过、count 不变
同组再连不减少分量
✗ 错：find 不压缩退化
✓ 对：while 里顺手 parent[x]=parent[parent[x]]
不压缩链会退化成 O(n)
完整代码（Java / Python / C++）
Java
class Solution {
int[] parent;
public int countComponents(int n, int[][] edges) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int count = n;
for (int[] e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra != rb) { parent[rb] = ra; count--; }
}
return count;
}
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
}Python
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
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:
vector<int> parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
int countComponents(int n, vector<vector<int>>& edges) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
int count = n;
for (auto& e : edges) {
int ra = find(e[0]), rb = find(e[1]);
if (ra != rb) { parent[rb] = ra; count--; }
}
return count;
}
};复杂度
时间
O((n+m)·α)
m 条边，每次 find 近乎常数（路径压缩）
空间
O(n)
一个 parent 数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 无向图中连通分量的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用并查集而不是 DFS/BFS？+
并查集天然按「合并」处理边流，增量维护分量数，且 find 近乎 O(1)；适合边动态加入的场景。
按秩合并有必要吗？+
只做路径压缩已近乎线性；再加按秩/按大小合并能让最坏复杂度严格到反阿克曼级，工程上常二者都上。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 无向图中连通分量的数目 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。