title: 并查集
date: 2022-11-15 11:49:57
tags: 算法

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时需要署名，推荐在我的个人博客阅读。

并查集是一种数据结构，用于合并两个集合以及判断两个集合是否联通。

初始化

for(int i=1;i<=n;i++)
    fa[i]=i; // 将每个点的祖先初始化为自己（创建n个集合）

并查集核心函数：找父亲

int findf(int t){
    if(fa[t]==t) // 自己是这个集合的祖先（自己代表这个集合）
        return fa[t]; // 返回id
    return findf(fa[t]); // 继续递归找
}

但是，这样的写法太过低效。可以证明，在极端数据下，会形成链，使查询效率变低。

所以，我们可以添加路径压缩来防止这个问题。

int findf(int t){
    if(fa[t]==t)
        return fa[t];
    return fa[t] = findf(fa[t]); // 修改的位置（记忆化）
}

合并

可以找到两个集合的代表，将一个集合设置为另一个集合。

void merge(int i,int j){
    fa[findf(i)]=findf(j); // 一行代码的事
}

判断是否为同一个集合

只需判断两个集合的代表是否为同一个。

bool equal(int i,int j){
    return findf(i)==findf(j); // 也是一行代码的事
}

模板题目及解析

P3379-【模板】并查集

纯粹的模板题目，应该不用说。

P1892-【BOI2003】团伙

因为题目中写道

• 一个人的朋友的朋友是朋友
• 一个人的敌人的敌人是朋友

所以开两倍大小的并查集，若 i , j 是朋友，合并 i , j ，若 i , j 是敌人，合并 i+n , j 和 i , j+n 。

判断时，若 i , j 联通，则是朋友，若 i+n , j 和 i , j+n 其中任一联通，则是敌人。