并查集

并查集 (Disjoint Set Union) 是一种树形的数据结构，顾名思义，它用于处理一些不交集的 合并 及 查询 问题。 裸的并查集支持两种操作：

• 查找（Find）：确定某个元素处于哪个子集；

• 合并（Union）：将两个子集合并成一个集合。

https://www.luogu.com.cn/problem/P1551

#include<bits/stdc++.h>

//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'

#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size(); ++iii) {cout << (x)[iii] << " \n"[iii==(x).size()-1];}
using namespace std;
#define mp make_pair
#define int long long

const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;

int fa[MAXN];
int cnt = 0;

int n, p, m;

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

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

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


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m >> p;
    init();
    int x, y;
    while (m--) {
        cin >> x >> y;
        merge(x, y);
    }
    while (p--) {
        cin >> x >> y;
        cout << (find(x) == find(y) ? "Yes" : "No") << '\n';
    }
}

权值维护

每个节点的权值特征都很容易维护。我们只要维护每个根结点的值，在合并或拆分时更新新的根节点值即可。这就是带权并查集。

路径压缩

我们可以在每一次查询过程中，将这个节点直接连接到根节点下面，使下次查询具有更快的速度。

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

启发式合并

合并时不同的决策可能影响这棵树的深度从而影响查询速度。具体来说，如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下，显然相比于将一棵点数与深度都较大的集合树连接到一棵更大的集合树下，接下来执行查找操作的用时更小。鉴于点数与深度这两个特征都很容易维护，我们常常从中择一，作为估价函数。当然，在算法竞赛的实际代码中，即便不使用启发式合并，代码也往往能够在规定时间内完成任务。

https://www.luogu.com.cn/problem/UVA11987

现有n个集合m个操作。规定第i个集合里为$\{i\}$。操作包括：

1. 输入两个元素 p 、 q ，如果 p 、q 不在一个集合中，合并这两个元素所在的集合。

2. 输入两个元素 p 、 q ，如果 p 、q 不在一个集合中，将 p 添到 q 所在的集合。

3. 输入一个元素 p ，查询 p 所在的集合的大小和元素和。

在本题中，1和3用带权并查集即可维护，而操作2我们却无法通过只修改p所指的根节点来完成。因为p可能是根节点，换句话说，p有子节点。这时候查询p的子节点就会出错。因此我们发现，当p为子节点，等价于p没有子节点时，我们修改p的根节点是没问题的。所以我们可以为每个实节点添加一个虚拟根节点，值为实节点的值加上一个偏移量offset，其中offset只需要大于等于最大的实点的值即可。这样经过路径压缩后，我们可以保证每一个实点都没有子节点，同时将数据维护在每个虚节点中，即可较为方便地解决问题。

#include<bits/stdc++.h>

//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'

#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size(); ++iii) {cout << (x)[iii] << " \n"[iii==(x).size()-1];}
using namespace std;
#define mp make_pair
#define int long long

const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;
int offset = 1e5 + 1;
int fa[MAXN], cnt[MAXN], sum[MAXN];

int n, p, m;

void init() {
    for (int i = 0; i <= offset; ++i) {
        fa[i] = i + offset;
        fa[i + offset] = i + offset;
        cnt[i + offset] = 1;
        sum[i + offset] = i;
    }
}

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

void merge(int i, int j) {
    int x = find(i), y = find(j);
    if (x == y)return;
    fa[y] = x;
    cnt[x] += cnt[y];
    sum[x] += sum[y];
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    while (cin >> n >> m) {
        init();
        int op, x, y, root;
        for (int i = 0; i < m; ++i) {
            cin >> op;

            switch (op) {
                case 1:
                    cin >> x >> y;
                    merge(x, y);
                    break;
                case 2:
                    cin >> x >> y;
                    root = find(x);
                    cnt[root]--;
                    sum[root] -= x;
                    root = find(y);
                    fa[x] = root;
                    cnt[root]++;
                    sum[root] += x;
                    break;
                case 3:
                    cin >> x;
                    root = find(x);
                    cout << cnt[root] << ' ' << sum[root] << '\n';
                default:
                    break;
            }
        }
    }
}

Reference

• https://oi-wiki.org/ds/dsu

• https://www.luogu.com.cn/blog/ThinkSongZe/solution-uva11987