title: 并查集
date: 2022-11-15 11:49:57
tags: 算法
本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。
并查集是一种数据结构，用于合并两个集合以及判断两个集合是否联通。
初始化
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 其中任一联通，则是敌人。