并查集

什么是并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

并查集支持两种操作：

• 合并（Union）：合并两个元素所属集合（合并对应的树）
• 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

重要 记得初始化

复杂度

时间复杂度

同时使用路径压缩和启发式合并之后，并查集的每个操作平均时间仅为 $O(\alpha(n))$ 。其中 $\alpha(n)$ 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

空间复杂度

显然为 $O(n)$。

例题

P3375 【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

对于 $100%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i, Y_i \le N$，$Z_i \in { 1, 2 }$。

输入格式

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

样例

输入

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出

N
Y
N
Y

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10009;
int fa[N]; // 存储每个节点的父节点
int find(int x)
{ // 如果 fa[x] == x 则x是该树的根节点
    return fa[x] == x ? x : find(fa[x]);
}
void merge(int a, int b)
{ // 合并两棵树
    a = find(a);
    b = find(b);
    if (a != b)
        fa[a] = b;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        fa[i] = i; // 初始化
    while (m--)
    {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1)
            merge(x, y);
        else
            cout << ((find(x) == find(y)) ? "Y" : "N") << '\n';
    }
    return 0;
}

板子

#include <cassert>
#include <iostream>
/* Last modified: 23/07/12 */
class DSU
{
  private:
    int *f;
    int size;

  public:
    DSU(int size)
    {
        assert(size > 1);
        this->size = size;
        f = new int[size + 10];
        for (int i = 1; i <= size; i++)
            f[i] = i;
        return;
    }
    int find(int x)
    {
        return f[x] == x ? x : (f[x] = find(f[x]));
    };
    bool same(int x, int y)
    {
        return DSU::find(x) != DSU::find(y);
    };
    int get_size()
    {
        return size;
    };
    int get_f(int i)
    {
        return f[i];
    };
    bool merge(int x, int y)
    {
        int fx = DSU::find(x);
        int fy = DSU::find(y);
        if (fx != fy)
        {
            f[fx] = fy;
            return true;
        }
        return false;
    };
};