c++中如何求图的连通分量_c++并查集实现图连通性判断

c++kquote>并查集通过find和union操作维护动态连通性，初始化各节点为独立集合，对每条边执行unite，最终统计不同根节点数得连通分量个数；需路径压缩与按size合并以保效率。

用并查集判断图连通性，核心是 find 和 union 操作

并查集（Union-Find）不是图遍历算法，而是高效维护动态连通关系的数据结构。它不直接“求连通分量”，但能快速回答「两点是否连通」，并在所有边处理完后，通过统计不同根节点数量得到连通分量个数。

关键点：初始化每个节点为独立集合；对每条无向边 (u, v) 执行 union(u, v)；最终调用 find(i) 统计不同根的数量。

• find 必须带路径压缩，否则多次查询可能退化成 O(n)
• union 推荐按秩合并（或按 size 合并），避免树过高
• 输入边时注意节点编号是否从 0 或 1 开始，影响数组大小分配

c++ 并查集标准实现（含路径压缩 + 按 size 合并）

下面是一个生产可用的轻量级实现，支持快速构建和连通分量计数：

struct UnionFind {     vector parent, size;     int components;      UnionFind(int n) : parent(n), size(n, 1), components(n) {         iota(parent.begin(), parent.end(), 0);     }      int find(int x) {         if (parent[x] != x) {             parent[x] = find(parent[x]); // 路径压缩         }         return parent[x];     }      void unite(int x, int y) {         x = find(x), y = find(y);         if (x == y) return;         if (size[x] < size[y]) swap(x, y);         parent[y] = x;         size[x] += size[y];         components--;     }      bool connected(int x, int y) { return find(x) == find(y); } };

使用示例：读入 n 个点、m 条边后统计连通分量数

立即学习“C++免费学习笔记（深入）”；

int n, m; cin >> n >> m; UnionFind uf(n); for (int i = 0; i < m; i++) {     int u, v; cin >> u >> v;     uf.unite(u, v); // 假设节点编号为 0~n-1 } cout << uf.components << endl;

如何获取每个连通分量的具体节点列表

components 字段只给总数，若需输出每个分量包含哪些点，得额外做一次分组：

• 遍历所有节点 i，用 find(i) 得到其根
• 用 map> 或 vector> 收集相同根的节点
• 注意：根不一定是原始编号，但每个分量内所有 find(i) 返回值一致

简写示例：

map> groups; for (int i = 0; i < n; i++) {     groups[uf.find(i)].push_back(i); } for (auto& [root, nodes] : groups) {     cout << "Component: ";     for (int x : nodes) cout << x << " ";     cout << "n"; }

容易忽略的边界与性能坑

实际编码中这几个点最常出错：

• 节点编号若从 1 开始，UnionFind uf(n) 没问题，但读入后要 u--, v-- 再传入
• 重边（重复的 (u,v)）不会破坏正确性，但 unite 中的 if (x==y) return 能避免冗余操作
• 离线静态图用并查集比 DFS/BFS 略快且内存更省；但若需实时删边，就得换动态图算法（如 ETT 树）
• 初始化 parent 用 iota 比循环赋值更简洁安全

连通分量本身没有顺序，但各分量内节点顺序取决于你遍历 0..n-1 的方式——这点在调试输出时容易让人误以为结果“不稳定”。