并查集¶

简介¶

并查集是一种简单直观的数据结构，其用于维护多个集合的成员关系，支持两种操作：

合并：将两个元素所属的集合进行合并。
查询：查询元素所属集合，这可以用于判断两元素是否在同一集合内。

并查集可以认为是一片森林，其中一个集合被视为一棵树，既同一集合的元素一定在同一棵树上。

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

并查集常作为其他算法的一部分出现，例如最小生成树。

初始化¶

我们定义数组 \(fat[i]\) 为元素 \(i\) 的父亲节点；方便起见，我们定义根节点的父亲节点为它本身；

对于初始情况，所有元素彼此独立，即 \(fat[i] = i\)。

const int MAXN = 1e5;

int fat[MAXN];

void init(){
    for (int i=0;i<MAXN;i++){
        fat[i] = i;
    }
    return ;
}

查询¶

对于两个元素查询其是否在同一集合内，其实就是查询这两个节点是否在同一棵树上。不难想到沿树向上找到根节点，再对根节点进行比对，如果根节点相同，那么这两个元素就在同一集合内。为了方便后续复用，此处find(int i)函数实际上是查询\(i\)元素所属树的根节点。

int find(int i){
    if (fat[i] == i) return i;
    else return find(fat[i]); 
}

路径压缩优化¶

不难看出，在查找的过程中所经过的每一个元素其实都属于同一集合，我们可以将这些元素直接连接到根节点，从而减少树的深度，加快查询速度，我们称这种方式为路径压缩。

int find(int i){
    if (fat[i] == i) return i;
    else return fat[i] = find(fat[i]); 
}

合并¶

对于两个元素合并其所属集合，其实就是合并\(i,j\)所在的树。不难想到通过将一棵树的根节点连接到另一棵树的根节点来实现。

void unite(int i, int j){
    fat[find(i)] = find(j);
}

启发式合并¶

合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

此处不再单独给出实现代码，参考：并查集-OI wiki

统计树的数量¶

有的时候，我们可能会需要计算并查集中维护的集合的数量，等价于树的数量。在这种情况下，我们可以通过统计 \(fat[i]==i\) 的元素数量来实现。

int count(int n){
    int cnt=0;
    for (int i=0;i<n;i++)
        if (fat[i]==i) cnt++;
    return cnt;
}

带权并查集¶

有时，传统并查集已经无法满足题目的要求，我们需要维护除了集合关系之外的其他信息。这个时候，我们就可以使用 带权并查集 来解决。

带权并查集 通过维护节点到根节点的附加信息（如距离、差值等），在保持高效合并与查询的同时扩展功能。以下是其核心实现与应用场景：

查询操作¶

定义 \(d[i]\) 表示节点 \(i\) 到父节点的权值。路径压缩时同步更新权值：

int find(int x){
    if (fat[x] != x){
        d[x] += d[dat[x]];
        fat[x] = find(fat[x]);
    }
    return fat[x];
}

合并操作¶

合并集合时，需根据题意调整权值。例如合并 \(a\) 和 \(b\) 且要保证 \(d[a] - d[b] = v\):

void unite(int a, int b){
    int fa = find(a), fb = find(b);
    if (fa != fb){
        fat[fa] = fb;
        d[fa] = d[b] - d[a] + v   // 根据约束条件推导
    }
}

并查集的其他用法¶

以信息学奥赛一本通中的 1430：家庭作业为例：

不难想到，先按照学分对作业进行降序排序，随后依次处理每个作业：先寻找最接近截止日期的可用时间段，若无可用时间段，则放弃该作业。

由于这道题的时限较短，使用 \(O(n^2)\) 的算法进行可用时间段的检验并不能通过这道题目。

这时，我们可以通过维护一个变种并查集的方式解决这个问题：

定义 \(fat[i]\) 代表时间点 \(i\) 的 『下一个可用时间点』 或 『前一个空闲时间点』。
当时间点 \(t\) 被占用时，令 \(fat[t] = find(t - 1)\) ，表示 『t被占用后，下一个可能空闲的时间点是 t-1』 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long

struct work {
    int ddl, score;
} works[10000005];

int fat[10000005];

bool cmp(work a, work b) {
    return a.score > b.score;
}

int find(int x) {
    if (fat[x] != x) {
        fat[x] = find(fat[x]);
    }
    return fat[x];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin >> n;

    int max_ddl = 0;
    for (int i = 0; i < n; ++i) {
        cin >> works[i].ddl >> works[i].score;
        if (works[i].ddl > max_ddl) {
            max_ddl = works[i].ddl;
        }
    }
    for (int i = 0; i <= max_ddl; i++) fat[i] = i;
    sort(works, works + n, cmp);

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int t = find(works[i].ddl);
        if (t > 0) {
            ans += works[i].score;
            fat[t] = find(t - 1);
        }
    }

    cout << ans;
    return 0;
}