洛谷【P1892 [BOI2003] 团伙】
反思：
- 这道题第一眼是并查集 但又不是普通并查集
- 我思路是卡在 如何处理 敌人的敌人的朋友身上
- 最后看题解学到了新思想：构造反集
- // 如果a和b是敌人，合并n+b和a，n+a和b
// 如果c和a是敌人，合并n+c和a，n+a和c
// 那么b和c就并在一起了
推导过程：
merge(b+n,a);
merge(a+n,b);
void merge(int x,int y){
int tx=find(x);
//1.find(n+a)
//1.2 find(n+a)=find(c);
int ty=find(y);
//2.find(c)
//2.2 find(b)
if(tx!=ty){
fa[tx]=ty;//如果祖先不相等 就让祖先节点相等
//3.fa[find(n+a]]=find(c)
//3,2 fa[find(c)]=find(b);合并成功
}
}
ac代码：
#include<bits/stdc++.h>
using namespace std;
// 如果a和b是敌人，合并n+b和a，n+a和b
// 如果c和a是敌人，合并n+c和a，n+a和c
// 那么b和c就并在一起了
int fa[2004];
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y){
int tx=find(x);
int ty=find(y);
if(tx!=ty){
fa[tx]=ty;//如果祖先不相等 就让祖先节点相等
// cout<<x<<" "<<y<<" "<<fa[tx]<<" "<<ty<<endl;
}
}
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=2*n;i++) fa[i]=i;//初始化
while(m--){
string A;
cin>>A;
int a,b;cin>>a>>b;
if(A=="E"){
//敌人就用反并查集
merge(b+n,a);
merge(a+n,b);
}else if(A=="F"){
merge(a,b);
}
}
int res=0;
for(int i=1;i<=n;i++)
{
// cout<<fa[i]<<endl;
if(fa[i]==i)
{
// cout<<i<<endl;
res++;
}
// if(fa[i])
}
cout<<res<<endl;
return 0;
}
原文地址：https://blog.csdn.net/2302_78926002/article/details/142687400
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！