扩展域并查集
可以维护类似于 P1892[BOI2003]团伙 的题目。
题目中有两种关系：朋友和敌人，并规定
- 一个人的朋友的朋友是朋友
- 一个人的敌人的敌人是朋友
引入反集的概念，例如有三个人 \(a,b,c\)，他们的反集为 \(a',b',c'\)。
如果 \(a,b\) 为敌人，连接 \(a,b'\) 和 \(a',b\)；
如果 \(a,b\) 为朋友，连接 \(a,b\)；
这样敌人的敌人恰好在一个连通块内，朋友的朋友也在一个连通块内，符合题意。
code
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1010;
int n,m,f[N<<1],ans;
int find(int x){
if(x==f[x])return x;
return f[x]=find(f[x]);
}
void add(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) f[fx]=fy;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=2*n;i++){
f[i]=i;
}
for(int i=1;i<=m;i++){
char opt[2];
int p,q;
scanf("%s%d%d",&opt,&p,&q);
if(opt[0]=='F'){
add(p,q);
// add(p+n,q+n); 没有说朋友的敌人也是敌人
}
else{
add(q+n,p);
add(p+n,q);
//父亲在1~n方便统计
}
}
for(int i=1;i<=n;i++){
if(f[i]==i) ans++;
}
printf("%d\n",ans);
return 0;
}