数据结构：并查集学习笔记

zaochen · 2022-12-30 10:23:22 · 个人记录

基础知识

并查集是一种树形数据结构。在全国青少年信息学奥林匹克系列竞赛大纲中难度为 6，是提高级中学习的数据结构。

并查集的基本操作：

查询一个元素在哪个集合。
合并两个集合。

使用一个森林来存储并查集，一个元素是一个结点，每棵树是一个集合。用一个数组 f 来记录父亲表示法。即 f[x] 表示元素节点 x 的父亲。这样，查询一个元素在哪个集合就是查询节点所在树的根节点，合并两个集合，就是把一颗树的根节点的父亲设置成另外一棵树的根节点。

并查集的优化

并查集有两种常用的优化操作，一种优化查询，一种优化合并。

查询：使用路径压缩，比较常用。容易发现，并查集只需要元素所在树的根节点，树的形态对操作没有影响。所以，可以在查询的时候，把所有查询的节点的父亲直接改成树根。（图来自《算法竞赛进阶指南》）

合并：使用启发式合并。把节点少的树合并到节点多的树上，通常在带权并查集中使用。这里不过多介绍，请参考拓展阅读相关资料。

并查集的代码实现

洛谷 P3367 【模板】并查集

并查集模板，要注意初始化，即每个元素所在的集合最开始只有自身。

#include <iostream>
using namespace std;

// 1. 并查集的存储
int f[100005], n; // 并查集中有 n 个元素

// 2. 并查集的查询（带路径压缩优化）
int get(int x)
{
    if (f[x] == x)
        return x; // x 是根节点
    return f[x] = get(f[x]); // 递归寻找根节点，并且进行路径压缩
}

// 3. 并查集的合并
void merge(int x, int y)
{
    f[get(x)] = get(y);
}

int main()
{
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i; // 4. 并查集的初始化
    while (m--) {
        int x, y, z;
        cin >> z >> x >> y;
        if (z == 1)
            merge(x, y);
        else {
            if (get(x) == get(y))
                cout << 'Y' << endl;
            else
                cout << 'N' << endl;
        }
    }
    return 0;
}

维护传递关系

并查集可以维护具有传递性的关系。也就是说，如果题目中出现的关系有如下性质：若 A 与 B 有这种关系，且 B 与 C 有这种关系，则 A 与 C 也有这种关系。如无向图中节点的连通性等。

洛谷 P1955 [NOI2015] 程序自动分析

思路：
变量之间的相等关系具有传递性。先把所有相等的变量用并查集合并，然后判断每个不等关系的条件，如果有两个变量不相等但是在同一集合内，则判断为不能满足，否则可以满足。所有条件可以被满足则约束关系可以被满足。另外，这题数据范围中的 i, j 较大，需要离散化处理数据。

参考代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1000005;
int t,fa[2*N],n,i1[N],i0[N],a1,j1[N],j0[N],a0;
int a[N],b[N],m;

int get(int x){
    return (fa[x]==x)?x:(fa[x]=get(fa[x]));
}

int query(int x){
    return lower_bound(b,b+m,x)-b;
}

int main(){
    ios::sync_with_stdio(0);
    cin >> t;
    while(t--){
        cin >> n; m=a1=a0=0; 
        for (int i=1;i<=2*n;i++) fa[i]=i;
        for (int i=1;i<=n;i++){
            int x,y,z;
            cin >> x >> y >> z;
            if (z==0) {
                a0++;
                i0[a0]=x,j0[a0]=y;
            } if (z==1) {
                a1++;
                i1[a1]=x,j1[a1]=y;
            }
            a[2*i-1]=x,a[2*i]=y;
        }
        sort(a+1,a+1+2*n);
        for (int i=1;i<=2*n;i++){
            if (i==1||a[i]!=a[i-1]) b[++m]=a[i];
        }
        for (int i=1;i<=a1;i++){
            fa[get(query(i1[i]))]=get(query(j1[i]));
        }
        bool flag=1;
        for (int i=1;i<=a0&&flag;i++){
            flag&=(get(query(i0[i]))!=get(query(j0[i])));
        }
        cout << ((flag)?("YES"):("NO")) << endl;
    }
    return 0;
}

统计并查集集合个数

在一些题中，需要我们统计并查集中集合个数。统计有多少树的根节点即可（根节点的父节点是他本身）我们来看下面这题：

洛谷 P1536 村村通

做法：
初始时，我们用并查集把所有直接连通的城镇合并。统计出集合数，显然集合数减一就是最少要建设的道路。

参考代码：

#include <iostream>
using namespace std;

int f[1005], n, m;
int get(int x)
{
    // 1. 并查集的查询，这里我用三元表达式压了下行
    return (f[x] == x) ? (x) : (f[x] = get(f[x]));
}

int main()
{
    ios::sync_with_stdio(0);
    do {
        cin >> n;
        if (n == 0)
            break;
        cin >> m;
        for (int i = 1; i <= n; i++)
            f[i] = i;
        for (int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            f[get(x)] = get(y); // 2. 并查集的合并
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans += (i == get(i)); // 3. 统计集合个数（就是统计根节点个数）
        cout << ans - 1 << endl;
    } while (n != 0);
    return 0;
}

带权并查集

有时候，我们除了需要并查集的两个基本操作外，还需要维护节点或者集合的一些其他信息。当我们维护集合的信息时，可以把信息记在集合的根节点上。当我们维护节点的信息是节点到根节点的距离或者其他与根节点相关的信息时，就使用边带权并查集，把信息记在节点到父节点的边上，在路径压缩时处理。

洛谷 P1196 [NOI2002] 银河英雄传说

思路：
维护两个战舰是否在同一列可以使用并查集。考虑如何维护战舰的位置。直接使用链表显然会超时，可以对链表进行路径压缩，记录每个节点到根节点的距离。合并时，把集合大小记在根节点上，把集合 A 合并到集合 B 上时，更新集合 B 的大小，并更新集合 A 根节点的信息，这样在路径压缩时就能传递到其他节点上。

参考代码：

#include <iostream>
using namespace std;

// 1. 带权并查集的定义(用结构体保存节点)
struct node {
    int fa, d, size;
    #define fa(i) f[i].fa
    #define d(i) f[i].d
    #define size(i) f[i].size
} f[30005];

// 2. 带权并查集的路径压缩查询
int get(int x) {
    if (fa(x) == x)
        return x;
    int root = get(fa(x));
    d(x) += d(fa(x));
    return fa(x) = root;
}

// 3. 带权并查集的合并(要维护根节点上的数据)
void merge(int x, int y) {
    int fx = get(x), fy = get(y);
    if (fx == fy)
        return;
    fa(fy) = fa(fx);
    d(fy) = size(fx);
    size(fx) += size(fy);
}

int t;

int main() {
    ios::sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif
    // 4. 初始化带权并查集
    for (int i = 1; i <= 30000; i++) {
        fa(i) = i;
        d(i) = 0;
        size(i) = 1;
    }

    cin >> t;
    while (t--) {
        char op;
        int i, j;
        cin >> op >> i >> j;
        if (op == 'M')
            merge(j, i);
        else {
            if (get(i) != get(j))
                cout << -1 << endl;
            else
                cout << abs(d(i) - d(j)) - 1 << endl;
        }
    }

    return 0;
}

拓展域并查集

在同时维护多种关系时，考虑使用拓展域并查集。即把每一个元素拆成多个元素，放到不同的域中。
具体的实现方法是，比如全部 n 个元素拆成 2 个域，A 域和 B 域，则 A 域中的 i 可以用 i 表示, B 域中的 i 可以用 n + i 表示。
由此可见，将 n 个元素的集合拆成 k 个域，所用的空间是 O(nk)。

洛谷 P1892 [BOI2003]团伙

朋友关系具有传递性，可以使用并查集。
对于敌人关系，可以拓展一个敌人域，如果两个人互为敌人，那就分别把两人和敌人域中两人合并。
最后统计集合个数即可。

参考代码：

#include <iostream>
using namespace std;

const int N = 1005;
int f[2 * N], n, m, ans; // 分成 2 个域要开 2 倍空间

int get(int x) {
    if (f[x] == x) return x;
    return f[x] = get(f[x]);
}

void merge(int x, int y) {
    f[get(x)] = get(y);
}

int main() {
    ios::sync_with_stdio(0);
    #ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    #endif
    cin >> n >> m;
    for (int i = 1;i <= 2 * n;i++) f[i] = i;
    for (int i = 1;i <= m;i++) {
        char op; int p, q;
        cin >> op >> p >> q;
        if (op == 'F') merge(p, q);
        else merge(n + p, q), merge(n + q, p);
    }
    for (int i = 1;i <= n;i++) if (f[i] == i) ans++;
    cout << ans << endl;
    return 0;
}

参考资料 && 拓展阅读 && 推荐题目

《深入浅出程序设计竞赛（基础篇）》，洛谷学术组编著，17.1 并查集
《算法竞赛进阶指南》，李煜东著，0x41 并查集
洛谷日报 #87[喵小皮]浅谈并查集优化
洛谷 P2256 一中校运会之百米跑提示：并查集+离散化/map
洛谷 P1551 亲戚提示：并查集维护传递关系
洛谷 P1111 修复公路提示：并查集+排序
洛谷 P8654 [蓝桥杯 2017 国 C] 合根植物提示：统计并查集集合个数
洛谷 P3958 [NOIP2017 提高组] 奶酪提示：并查集+数学
洛谷 P2814 家谱提示：并查集+离散化/map
洛谷 P1455 搭配购买提示：并查集+01背包
洛谷 P2024 [NOI2001] 食物链提示：拓展域并查集

数据结构：并查集 学习笔记

基础知识

并查集的优化

并查集的代码实现

洛谷 P3367 【模板】并查集

维护传递关系

洛谷 P1955 [NOI2015] 程序自动分析

统计并查集集合个数

洛谷 P1536 村村通

带权并查集

洛谷 P1196 [NOI2002] 银河英雄传说

拓展域并查集

洛谷 P1892 [BOI2003]团伙

参考资料 && 拓展阅读 && 推荐题目

数据结构：并查集学习笔记