poj 1182

http://poj.org/problem?id=1182

一个利用并查集的经典题目。

思路：在网上看到别人的思路，觉得方法还是挺不错的。

首先，开辟一个3*n的数组belg，用来存b和c的关系，在belg[c+m]存，c是被谁吃的，belg[c+2*m]存b是吃谁的。

bool judge(int x,int y) {return (Find(x)==Find(y));}

如果judge（b,c+m）和 judge（b，c+2*m）都为假的话，那么可以说明，b和c是在同类。

然后合并b,c。b+m,c+m。b+2m,c+2m。

第一个judge可以判断，b不会吃c,第二个Judge可以判断c也不会吃b，所以，b,c肯定是同类。

如果judge（b,c）和judge(b,c+2*m)都为假的话，那么可以说明，c是被b吃的，然后合并b,c+m。b+m，c+2*m。b+*2m，c；

第一个judge可以判断b和c不是同一类，第二个judge可以判断c不会吃b，那么就可以说明c是被b吃的。c是被b吃的，那么说明，c+m存的就是b，所以c+m和b合并。之后的也是同样的意思。

 #include <stdio.h>

 #include <string.h>

 int belg[];

 int Find(int x)   //Find 的迭代写法。

 {

     int _x=x,_b;

     while(_x!=belg[_x])

     {

         _x=belg[_x];

     }

     while(x!=belg[x])

     {

         _b=belg[x];

         belg[x]=_x;

         x=_b;

     }

     return _x;

 }

 bool judge(int x,int y) {return (Find(x)==Find(y));}

 void unite(int x,int y)

 {

     int root1=Find(x);

     int root2=Find(y);

     if(root1!=root2) belg[root1]=root2;

 }

 int main()

 {

     int m,n,a,b,c,ans=;

   //  freopen("in.txt","r",stdin);

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

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

         belg[i]=i;

     while(n--)

     {

         scanf("%d%d%d",&a,&b,&c);

         if(b>m||c>m) ans++;

         else if(a==)

         {

             if(judge(b,c+m)||judge(b,c+*m)) ans++;

             else {     //b,c是同类时，合并所有的信息。

                 unite(b,c);

                 unite(b+m,c+m);

                 unite(b+*m,c+*m);

             }

         }

         else {

             if(judge(b,c)||judge(b,c+*m)) ans++;

             else {     //b,c不是同类时，合并那些是同类的信息。

                 unite(b,c+m);

                 unite(b+m,c+*m);

                 unite(b+*m,c);

             }

         }

     }

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

     return ;

 }

巴特西

poj 1182

最新文章

热门文章