C++并集查找

并查集（Union-Find / DSU） 是算法竞赛和工程中最常用的数据结构之一，主要解决动态连通性问题，即：

• 判断两个元素是否在同一个集合（连通分量）中
• 合并两个集合

时间复杂度在路径压缩 + 按秩/按大小合并后，单次操作均摊近似 O(1)（严格说是 α(n)，阿克曼函数反函数，实际几乎是常数）。

1. 最推荐的 C++ 现代写法（2025-2026 竞赛常用模板）

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> parent;   // 父节点
    vector<int> rank;     // 秩（树的高度上界）或 size（集合大小）
    vector<int> size;     // （可选）集合实际大小

    // 构造函数：初始化 n 个元素（下标通常从 0 或 1 开始）
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);     // 初始秩为 0
        size.resize(n, 1);     // 每个集合初始大小 1
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    }

    // 查找根节点 + 路径压缩（非递归写法，更安全）
    int find(int x) {
        while (x != parent[x]) {
            // 隔代压缩（比全压缩更稳，实际效果接近）
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;

        // 更激进的递归路径压缩（常用，但栈可能溢出大 n）
        // return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    // 判断是否同集合
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并 x 和 y 所在集合（按秩合并）
    bool unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx == ry) return false;  // 已同集合，不合并

        // 按秩合并：小的秩挂到大的秩下面
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry;
            size[ry] += size[rx];
        } else {
            parent[ry] = rx;
            size[rx] += size[ry];
            if (rank[rx] == rank[ry]) {
                rank[rx]++;  // 只有等高时才增加秩
            }
        }
        return true;
    }

    // （可选）获取 x 所在集合的大小
    int getSize(int x) {
        return size[find(x)];
    }

    // （可选）获取当前连通分量个数（需额外维护 cnt 变量）
};

2. 按大小合并 vs 按秩合并（二选一即可）

很多现代模板更推荐按大小合并，因为：

• 代码更简单
• 实际效果几乎一样好
• size 还能直接用来求集合大小

按大小合并版本（替换 unite 函数即可）：

bool unite(int x, int y) {
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) return false;

    // 小的集合挂到大的集合下
    if (size[rx] < size[ry]) {
        swap(rx, ry);           // 保证 rx 是大的
    }
    parent[ry] = rx;
    size[rx] += size[ry];
    return true;
}

3. 经典使用场景代码示例

例1：判断连通 + 合并（洛谷 P3367 模板题风格）

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n + 1);  // 1~n

    while (m--) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {
            uf.unite(a, b);
        } else {
            cout << (uf.same(a, b) ? "Y" : "N") << '\n';
        }
    }
}

例2：求连通分量个数（额外维护 cnt）

struct UnionFind {
    // ... 其他同上
    int cnt;  // 连通分量数

    UnionFind(int n) : cnt(n) {
        // ... 其他初始化
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        // 合并逻辑...
        cnt--;           // 每次真正合并，连通分量 -1
        return true;
    }
};

4. 常见变种（快速了解）

变种	核心改动	典型题目类型
带权并查集	维护到根的权值（如距离、异或值）	带关系的食物链、距离查询
可撤销并查集	用栈记录历史操作，或按时间分治	离线查询、历史版本
按时间合并	小到大合并 + 启发式合并	动态加边求连通性
二维并查集	下标转一维 或 用 pair	网格连通、岛屿问题

5. 小Tips & 防坑

• 下标从 0 还是从 1？统一想好，比赛最容易错这里
• n 很大（1e6~1e7）时，用 vector 比数组更安全
• find 用非递归隔代压缩最稳（防止递归栈爆）
• 不要在 find 里写 cout 或复杂操作（影响效率）
• 合并前一定要 find，直接 parent[x]=y 会错

你现在是想：

1. 直接抄这个模板刷题？
2. 看带权并查集（食物链那种）的写法？
3. 要某个具体题目的代码（合根植物 / 岛屿数量 / 冗余连接 等）？
4. 还是想了解路径压缩为什么几乎是 O(1)？

告诉我，我继续给你展开～