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

并查集通过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 条边后统计连通分量数

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";
}