323. 无向图中连通分量的数目（中等）

Blind 75 › 323. 无向图中连通分量的数目（中等） （第 6 章）
文章工具

题目

给定 n 个节点，编号从 0 到 n-1，再给出一组无向边 edges。把「能通过若干条边互相到达」的节点归到同一个连通分量，问这张图里总共有几个连通分量。

换句话说：把节点看成人，每条边表示两人是朋友；朋友关系会传递，最终这张关系网会被分成几个互不相通的圈子，问圈子个数。

自造示例：n = 7，edges = [[0,1],[1,2],[3,4],[5,6]] → 3。其中 0-1-2 是一块，3-4 是一块，5-6 是一块。

约束：n 为 1 ~ 2000；边数 m 为 0 ~ 5000；每条边两个编号均在 0 ~ n-1；无重边、无自环。

思路

一句话：把「连成一片」看成等价关系，用并查集维护每个节点所属的分量；每处理一条边，最多让分量数减 1。

最直白的做法是 DFS/BFS：从任意未访问节点出发，把整片能到达的节点都标记完，分量数 +1；重复直到所有节点都访问过。它已经能做到 O(n+m)，也很好理解。

但它更偏「离线」：必须先建邻接表、维护 visited，整张图固定后才能一次算完；如果题目升级成「边一条条加入、随时询问现在有几块」，每次都要重新搜索。

关键观察：初始时每个节点自成一个分量，共 n 块。一条边 (a,b) 只会有两种结果：

  • a、b 已经在同一块：这条边是冗余的，分量数不变；
  • a、b 在不同块：这条边把两块合并成一块，分量数 -1。

于是问题变成「不断把两个集合合并、判断两个元素是否已经在同一集合」。这正是并查集的用武之地：它不存整张邻接表，只维护「每个节点最终归属哪个代表元」。

选用「按大小合并 + 路径压缩」的并查集：单次查询/合并摊销约 O(α(n))，总体近乎 O(n+m)，空间 O(n)。

解法

用并查集维护每个节点所在分量的代表元，步骤：

  1. 初始化：parent[i] = i，每个节点都是自己的代表；component = n。
  2. 对每条边 (a,b)，分别找出 a、b 所在分量的根。
  3. 若两个根不同：把较小集合挂到较大集合下，component 减 1。
  4. 若两个根相同：说明已经在同一分量，不处理。
  5. 返回 component。

以 n = 6，edges = [[0,1],[2,3],[4,5],[1,2],[0,2]] 走一遍：

步骤当前边判断分量数
初始—每个点各成一块6
10-1不同根，合并5
22-3不同根，合并4
34-5不同根，合并3
41-2不同根，两块合并2
50-2已同根，跳过2

注意第 5 步：虽然边存在，但两端早已在同一块，真正的合并次数才决定分量数。

下图把上面 5 个步骤串成流程，并逐步演示：

323. 无向图中连通分量的数目（中等） 解法步骤流程图
图① 解法步骤流程图（共 5 步）。
323. 无向图中连通分量的数目（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 int countComponents(int n, vector<vector<int>>& edges) {
 pare
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。