NameGod 的并查集基本操作学习笔记

OI WIKI

核心思想

并查集（Disjoint Set Union, DSU） 是一种处理不相交集合合并与查询的数据结构。

显然吧，由定义来看支持以下的两种操作：

合并：两集合合并。

查找：判断元素属于哪个集合。

代码实现

我们开始写代码。

初始化：

const int MAXN = 2e5 + 5;
int fa[MAXN]; // 存储每个元素的父节点

void init() {
    for (int i = 1; i <= N; ++i) {
        fa[i] = i;
    }
}

初始化时，显然每个点都独立地形成一个集合，不妨将每个节点的父亲设为自己。

查询：

很显然，我们需要沿着树向上移动，直至找到根节点，根节点就是所要查找的集合的父亲。

int find(int cur) {
    if (fa[cur] == cur)
        return cur;
    else return find(fa[cur]);
}

如果父亲已经是自己，那么已经找到了这个集合的父亲。如果父亲不是自己，那么就递归找自己的父亲。

很显然这个方法时间复杂度常数有点大，考虑一下记忆化，即路径压缩：

int find(int cur) {
    if (fa[cur] == cur)
        return cur;
    else return fa[cur] = find(fa[cur]);
}

查询过程中经过的每个节点必然也同属于该集合，不妨其直连到根节点以加快后续查询。

这样重复的查询只会查一次，时间复杂度常数明显进步。

时间复杂度 O(α(n))

合并

合并，合并，只要将一棵树的根节点连到另一棵树的根节点就好了。

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

很显然这个方法时间复杂度常数虽然不大，但合并的时候，选择哪棵树的根节点作为新树的根节点会影响未来查找函数的复杂度，将节点较少或深度较小的树连到另一棵，以免发生退化，考虑一下启发式合并：

const int MAXN = 2e5 + 5;
int fa[MAXN]; // 存储每个元素的父节点
int siz[MAXN]; // 储存对应集合的大小

void init() {
    for (int i = 1; i <= N; ++i) {
        fa[i] = i;
        siz[i] = 1;
    }
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry)
        return;
  if (siz[rx] < siz[ry])
    swap(rx, ry); // 确保rtx是较大集合，rty是较小集合
  fa[ry] = rx; // 小集合挂到大集合
  siz[rx] += siz[ry]; // 更新集合大小
}

如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下，显然相比于另一种连接方案，接下来执行查找操作的用时更小（也会带来更优的最坏时间复杂度）。

时间复杂度 O(α(n))

完整模板

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

const int MAXN = 2e5 + 5; // 根据题目要求调整大小
int fa[MAXN]; // 存储每个元素的父节点
int siz[MAXN]; // 存储每个集合的大小

// 初始化并查集
void init(int N) {
    for (int i = 1; i <= N; ++i) {
        fa[i] = i; // 每个元素初始父节点为自己
        siz[i] = 1; // 每个集合初始大小为1
    }
}

// 查找操作（带路径压缩）
int find(int cur) {
    if (fa[cur] == cur)
        return cur;
    return fa[cur] = find(fa[cur]); // 路径压缩
}

// 合并操作（带按大小合并优化）
void merge(int x, int y) {
    int rx = find(x); // 找到x的根节点
    int ry = find(y); // 找到y的根节点
    // 如果已在同一集合，直接返回
    if (rx == ry)
      return;
    // 确保rx是大集合，ry是小集合
    if (siz[rx] < siz[ry]) 
        swap(rx, ry);
    // 将小集合挂到大集合下
    fa[ry] = rx;
    // 更新大集合的大小
    siz[rx] += siz[ry];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N, M; // N个元素，M个操作
    cin >> N >> M;
    init(N); // 初始化并查集
    while (M--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            // 合并操作
            merge(x, y);
        }
          else if (op == 2) {
            // 查询操作
            cout << (find(x) == find(y) ? "Y\n" : "N\n");
        }
    }
    return 0;
}