扩展域并查集——基本原理与实现方式-爱代码爱编程
并查集算法可以说是所有提高组算法中最友好的算法之一,就算是它的路径压缩也很好打。但是,对于某些题,朴素的并查集可能无法得出正确答案。例如这道题。
[BOI2003]团伙
题目描述
现在有 n 个人,他们之间有两种关系:朋友和敌人。我们知道:
一个人的朋友的朋友是朋友
一个人的敌人的敌人是朋友
现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。
输入格式
第一行输入一个整数 n 代表人数。
第二行输入一个整数 m 表示接下来要列出 m 个关系。
接下来 m 行,每行一个字符 opt 和两个整数 p,q,分别代表关系(朋友或敌人),有关系的两个人之中的第一个人和第二个人。其中 opt 有两种可能:
- 如果 opt 为 `F`,则表明 p 和 q 是朋友。
- 如果 opt 为 `E`,则表明 p 和 q 是敌人。
输出格式
一行一个整数代表最多的团体数。
样例 #1
样例输入 #1
6
4
E 1 4
F 3 5
F 4 6
E 1 2
样例输出 #1
3
提示
对于 100% 的数据,2≤n≤1000,1≤m≤5000,1≤p,q≤n。
扩展域并查集
浓缩一下题意,我们发现题目要求我们维护的不仅仅是联通关系,还有不连通关系。而我们清楚的知道,并查集能维护的只有联通关系。那么这一题该怎么做呢?
答案就是本篇所提的扩展域并查集!
原理:
扩展域并查集显著的特征就是开了多倍并查集,也就是多倍father数组。首先审审刚才那个题,两个人只有两种情况:在同一团伙和不在同一团伙。那我们就开两倍并查集。开两倍并查集代表了什么呢?相当于我们给每个成员创建了一个分身。如果我们根据以下规则对其进行合并,最终结果一定是正确的。
合并规则:
首先需要明确,数组中的元素fa[x]指的是成员本身的父节点,fa[x+n]指的是成员的分身的父节点。
如果两个成员是朋友:那我们就把两个成员本身进行合并。
如果两个成员不是朋友:那我们就分别把一个成员本身和另一个成员的分身合并。
分身的理解:如果a成员和b成员分身在一个集合,那么a成员必定不和b成员在一个集合,简单粗暴一点就是一个占位的。
合并这里有一些注意的点,会在后面的代码注释里提及。
查询规则:
定义一个计数器tot,我们从1开始遍历到n,每找到一个根节点就tot++,最终tot就是团伙的个数。
注意:为了保证所有团伙的根节点都位于1--N,我们要在合并时做一些小修改。
代码实现:
具体代码实现:
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v;
int fa[2500];//开两倍并查集
int find(int x){
//普通的find函数和路径压缩。
if(fa[x]!=x)fa[x]=find(fa[x]);
return fa[x];
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;//输入n,m
char c;
for(int i=1;i<=2*n;i++){
fa[i]=i;
}//对两倍并查集进行初始化,1-n是本身,n+1-2n是分身。
for(int i=1;i<=m;i++){
cin>>c>>u>>v;
if(c=='F'){//朋友情况
fa[find(u)]=find(v);//只将本身合并即可
}else{
fa[find(u+n)]=find(v);
fa[find(v+n)]=find(u);
/*重点!这里不可以写成:
fa[find(u)]=find(v+n);
fa[find(v)]=find(u+n);
这意味着你将本身指向了分身,这是不可以的。
这样会导致集合的根节点跑到了分身那一边去,如果我们只遍历本身一侧,则答案会变小。
如果执意这样写或混合写,你只能在遍历找根的地方把范围改成1-2n。
但本着节约时间的原则,我们最好不这样写。
*/
}
}
int tot=0;//定义计数器
for(int i=1;i<=n;i++){
if(fa[i]==i){//寻找根节点:原理为一棵树有且只有一个根
tot++;
}
}
cout<<tot;//输出答案
return 0;
}
附录:
对于一些卡常的并查集题我们可以使用启发式合并,具体请见本人这篇文章。
完结撒花~~~