【Baltic2003】【BZOJ1370】Gang團伙(並查集,拆點)

NO IMAGE

problem

  • 給定n個人
  • 朋友的朋友是朋友,敵人的敵人是朋友
  • 朋友之間組成一個團伙,求團伙數

solution

  • 將每個點x拆成兩個:x和x n(分別表示x的朋友和敵人)
  • 如果x和y是朋友,就將x和y合併
  • 如果x和y是敵人,就將x和y n合併,將y和x n合併
  • 注意朋友的敵人不一定是敵人,因此如果x和y是朋友,不能將x n和y n合併

codes

#include<iostream>
#include<algorithm>
#define maxn 1010
using namespace std;
//UnionFindSet
int fa[maxn<<1];
void init(int n){for(int i = 1; i <= n; i  )fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x==y)return;fa[x]=y;}
int main(){
int n, m;
cin>>n>>m;
init(maxn<<1);
for(int i = 1; i <= m; i  ){
char op;  int x, y;
cin>>op>>x>>y;
if(op=='F'){
merge(x,y);
//merge(x n,y n);
}else{
merge(x,y n);
merge(x n,y);
}
}
int a[maxn];
for(int i = 1; i <= n; i  )
a[i]=find(i);
sort(a 1,a n 1);
int ans = 0;
for(int i = 1; i <= n; i  )
if(i==1 || a[i]!=a[i-1])
ans  ;
cout<<ans<<'\n';
return 0;
}