并查集学习笔记

· · 个人记录

前置知识：树的父亲表示法。

并查集基础

并查集，又称 DSU，是一个可以动态维护若干个不重叠的集合的数据结构。

并查集支持的基本操作有两种：

  1. 查询一个元素在哪一个集合里。
  2. 合并两个集合。

并查集的思想是将每一个集合存储为一棵有根树，以树根为这棵树的代表。我们可以记录一个 fa 数组，存储每一个节点的父亲节点，在合并集合的时候，查询两个节点的根，把一个节点的根接到另外一个节点的根上，就可以合并集合了。

优化

但是，这棵有根树可能退化成链，单次查询的时间复杂度就会退化成 O(n)。怎么办呢？因为我们只关心一棵树的根，不关心树的具体形态，所以这两棵树是等价的：

路径压缩

我们可以使用“路径压缩”的思想，在查询一个节点 x 的根时，直接将 fa_x 设为 root_x。使用路径压缩优化以后，每一次查询的均摊时间复杂度变为 O(\log n)。

按秩合并

还有一种优化方法，就是“按秩合并”。在每一个节点上多维护一个 siz 数组，表示当前节点子树的大小。当合并两棵树时，将 siz 小的树合并到 siz 大的树上，只增加 siz 小的树的查询代价。使用按秩合并优化以后，每一次查询的均摊时间复杂度也是 O(\log n)。

同时使用路径压缩优化和按秩合并优化的并查集，每一次查询的均摊时间复杂度可看作一个常数忽略不计，与 O(1) 相近。

一般在使用并查集时，我们只需要使用路径压缩优化就够了。

模板题代码：

#include <iostream>

using namespace std;

int n, m, p, f[10001], u, v;
int getfa(int x){
    if (f[x] == x) return x;
    return f[x] = getfa(f[x]);
}
void merge(int a, int b){
    f[getfa(a)] = getfa(b);
}
bool check(int a, int b){
    return getfa(a) == getfa(b);
}
int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i ++) f[i] = i;
    for (int i = 1;i <= m;i ++){
        cin >> p >> u >> v;
        if (p == 1) merge(u, v);
        else {
            if (check(u, v)) cout << "Y\n";
            else cout << "N\n";
        }
    }
}

“扩展域”与“边带权”的并查集

有时候，一般的并查集无法维护题目中各种各样的传递关系，我们就可以使用“扩展域”与“边带权”的并查集。

拓展域

“拓展域”，顾名思义就是把一个节点拆成多个节点，记录所有情况，合并时将所有情况都合并。

边带权

“边带权”，顾名思义也就是将维护的无权树变为有权树，边的权可以记录一些信息。而路径压缩后，x 到根的边权，也就是路径压缩前 x 到根经过的所有边边权合并后得到的结果。

例题

【模板】并查集

[NOI2015] 程序自动分析

Supermarket

[NOI2002] 银河英雄传说

[CEOI1999] Parity Game

[NOI2001] 食物链

[NOIP2010 提高组] 关押罪犯

石头剪子布