【模板】并查集

GitHub跳转原题关系图返回列表

用并查集维护若干元素所属的集合，操作 1 合并两个集合，操作 2 判断两个元素是否已经连通。

OJ: luogu

题目 ID: P3367

难度:入门

标签:并查集模板题

日期: 2026-06-20 00:14

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

题目给出 n 个元素和 m 次操作。

操作有两种：

  1. 合并 x 和 y 所在的集合；
  2. 询问 x 和 y 是否在同一个集合。

如果在同一个集合里输出 Y，否则输出 N。

思路

先看一个小数据暴力：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> comp(n + 1);
    for (int i = 1; i <= n; i++) {
        comp[i] = i;
    }

    for (int i = 1; i <= m; i++) {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            if (comp[x] == comp[y]) {
                continue;
            }
            int old_id = comp[y];
            int new_id = comp[x];
            for (int j = 1; j <= n; j++) {
                if (comp[j] == old_id) {
                    comp[j] = new_id;
                }
            }
        } else {
            cout << (comp[x] == comp[y] ? 'Y' : 'N') << '\n';
        }
    }

    return 0;
}

暴力的做法是给每个点记录一个“当前集合编号”：

  • 合并时，把其中一个集合的所有点都改成另一个集合编号
  • 询问时，直接比较两个编号是否相同

这个方法很好理解，但每次合并都可能扫一遍全部元素，复杂度太高。

正式做法就是并查集模板。

并查集维护两件事：

  • fa[x]：点 x 当前的父节点
  • find(x)：一路向上找到它所在集合的代表元

如果两个点的代表元相同，就说明它们在同一个集合里。

为了让复杂度足够低，常用两个优化：

  1. 路径压缩：find(x) 之后，把路径上的点直接挂到根上；
  2. 按大小合并：让小集合挂到大集合下面，避免树太高。

这样：

  • 合并操作就是把两个根连起来；
  • 查询操作就是比较两个根是否相同。

代码

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

const int MAXN = 200005;

int n, m;
int fa[MAXN], sz[MAXN];

void init_dsu(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

void unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) {
        return;
    }
    if (sz[x] < sz[y]) {
        swap(x, y);
    }
    fa[y] = x;
    sz[x] += sz[y];
}

bool same(int x, int y) {
    return find_root(x) == find_root(y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    init_dsu(n);

    for (int i = 1; i <= m; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            unite(x, y);
        } else {
            cout << (same(x, y) ? 'Y' : 'N') << '\n';
        }
    }

    return 0;
}

复杂度

使用路径压缩和按大小合并后，单次操作的均摊复杂度近似常数。

总时间复杂度可以认为是：

O(mα(n))O(m \alpha(n))

其中 α(n) 是反阿克曼函数，在竞赛范围内几乎可以看成常数。

空间复杂度 O(n)O(n)。

总结

这题就是并查集最基础的模板题。真正要记住的不是代码本身，而是并查集适合处理什么问题：合并集合、查询是否同属一个集合。