BZOJ 1370 团伙

两个认识的人不是朋友就是敌人，且满足：

1，朋友的朋友是朋友；

2，敌人的敌人是朋友。

一群朋友组成一个团伙，给出m个信息，求有多少个团伙。

用并查集，把一个点x拆成x和x’

若a与b为朋友，则将a与b所在集合合并，这样就满足朋友的朋友是朋友；

若a与b为敌人，则将a’与b所在集合合并，将a与b’所在集合合并；这样如果a与b，b与c为敌人，那么a与b’合并，b'与c合并，则a与c在同个集合，满足敌人的敌人是朋友。

最后，统计点1~n所属于的集合的个数即为答案。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int fa[],a[],p,x,y,n,m,ans=;

 void read(int &k){

     k=; int f=; char c=getchar();

     while (c<''||c>'')c=='-'&&(f=-),c=getchar();

     while (''<=c&&c<='')k=k*+c-'',c=getchar();

     k*=f;

 }

 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

 int main(){

     read(n); read(m);

     for (int i=;i<=*n;i++) fa[i]=i;

     for (int i=;i<=m;i++){

         char c=getchar();

         read(x); read(y);

         if (c=='F') fa[find(x)]=find(y);

         else{

             fa[find(x)]=find(y+n);

             fa[find(y)]=find(x+n);

         }

     }

     for (int i=;i<=n;i++) a[i]=find(i);

     sort(a+,a+n+);

     for (int i=;i<=n;i++) if (a[i]!=a[i-]) ans++;

     printf("%d\n",ans);

     return ;

 }

巴特西

BZOJ 1370 团伙

最新文章

热门文章