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

用并查集判断图连通性，核心是 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++免费学习笔记（深入）”；

BlessAI

Bless AI 提供五个独特的功能：每日问候、庆祝问候、祝福、祷告和名言的文本生成和图片生成。

下载

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 的方式——这点在调试输出时容易让人误以为结果“不稳定”。