【并查集】BZOJ1370- [Baltic2003]Gang团伙

【题目大意】

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、我朋友的朋友是我的朋友； 2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

【思路】

水………NOIP的小孩都不屑于玩……

把i拆成i和i+n,其中i表示i的朋友，i+n表示i的敌人。对于(i,j):

(1)i，j是朋友，那么合并i和j。

(2)i，j不是朋友，那么合并i和j+n,j和i+n，代表敌人的敌人是我的朋友。

*注意，如果i和j是敌人，那么它们的敌人不一定是朋友。所有不要合并i+n和j+n。

好水啊……

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 int u[MAXN],h[MAXN],appear[MAXN];

 int n,m,gang;

 int find(int x)

 {

     int r=x,temp;

     while (u[r]!=r) r=u[r];

     while (x!=r)

     {

         temp=u[x];

         u[x]=r;

         x=temp;

     }

     return r;

 }

 void union_set(int fa,int fb)

 {

     if (h[fa]>=h[fb])

     {

         u[fb]=fa;

         if (h[fa]==h[fb]) h[fa]++;

     }

     else u[fa]=fb;

 }

 void init()

 {

     for (int i=;i<=*n;i++)

     {

         u[i]=i;

         h[i]=;

     }

 }

 void solve()

 {

     scanf("%d%d",&n,&m);

     init();

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

     {

         char op[];

         int u,v;

         scanf("%s%d%d",op,&u,&v);

         if (op[]=='F')

         {

             int fa=find(u),fb=find(v);

             if (fa!=fb) union_set(fa,fb);

         }

         else

         {

             int fa=find(u),fb=find(v+n);

             if (fa!=fb) union_set(fa,fb);

             fa=find(v),fb=find(u+n);

             if (fa!=fb) union_set(fa,fb);

         }

     }

 }

 void getans()

 {

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

     memset(appear,-,sizeof(appear));

     gang=;

     for (int i=;i<=n;i++)

     {

         if (appear[u[i]]==-)

         {

             gang++;

             appear[u[i]]=;

         }

     }

     printf("%d",gang);

 }

 int main()

 {

     solve();

     getans();

     return ;

 }

巴特西

【并查集】BZOJ1370- [Baltic2003]Gang团伙

最新文章

热门文章