poj 1703 find them,catch them

这个题目是典型的种类判断的并查集，种类判断的并查集似乎无一例外的全部用到了relation（与祖先的关系），然后就是找关系化简式子然后套用种类判断并查集的通常做法就好。这个题目就是告诉你，现在一个城市里面有两个帮派，任何一个帮派分子不是属于这个帮派就是属于另一个帮派。现在告诉你现在有多少帮派分子，然后有m句话，其中A开头的表示询问这两个人的关系如何，D是告诉你这两个人不是一伙的。附代码。

[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<stdio.h>
using namespace std;
int father[100000+10];
int relation[100000+10];
int flag;
int find_ant(int x)
{
    if(x!=father[x])
    {
        int temp=father[x];;
        father[x]=find_ant(father[x]);
        relation[x]=(relation[x]+relation[temp])%2;
    }
    return father[x];
}
void unin(int x,int y)
{
    int x_x,y_y;
    x_x=find_ant(x);
    y_y=find_ant(y);
    if(x_x!=y_y)
    {
        father[y_y]=x_x;
        relation[y_y]=(relation[x]+relation[y]+1)%2;
    }
    else {
        if(relation[x]==relation[y])
            flag=1;
        else flag=0;
    }
}
int main()
{
    int T,a,b,n,m,i,p,q;
    char c;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
            father[i]=i;
            relation[i]=0;
        }
        for(i=1;i<=m;i++)
        {
            getchar();
            c=getchar();
            scanf("%d%d",&a,&b);
            if(c=='A')
            {
                p=find_ant(a);
                q=find_ant(b);
                if(p!=q)
                    cout<<"Not sure yet."<<endl;
                else {
                    unin(a,b);
                    if(flag==1)
                        cout<<"In the same gang."<<endl;
                    else cout<<"In different gangs."<<endl;
                }
            }
            else if(c=='D')
            {
                unin(a,b);
            }
        }
    }
    return 0;
}

</SPAN>

#include<iostream>
#include<stdio.h>
using namespace std;
int father[100000+10];
int relation[100000+10];
int flag;
int find_ant(int x)
{
if(x!=father[x])
{
  int temp=father[x];;
  father[x]=find_ant(father[x]);
  relation[x]=(relation[x]+relation[temp])%2;
}
return father[x];
}
void unin(int x,int y)
{
int x_x,y_y;
x_x=find_ant(x);
y_y=find_ant(y);
if(x_x!=y_y)
{
  father[y_y]=x_x;
  relation[y_y]=(relation[x]+relation[y]+1)%2;
}
else {
  if(relation[x]==relation[y])
   flag=1;
  else flag=0;
}
}
int main()
{
int T,a,b,n,m,i,p,q;
char c;
cin>>T;
while(T--)
{
  cin>>n>>m;
  for(i=1;i<=n;i++)
  {
   father[i]=i;
   relation[i]=0;
  }
  for(i=1;i<=m;i++)
  {
   getchar();
   c=getchar();
   scanf("%d%d",&a,&b);
   if(c=='A')
   {
    p=find_ant(a);
    q=find_ant(b);
    if(p!=q)
     cout<<"Not sure yet."<<endl;
    else {
     unin(a,b);
     if(flag==1)
      cout<<"In the same gang."<<endl;
     else cout<<"In different gangs."<<endl;
    }
   }
   else if(c=='D')
   {
    unin(a,b);
   }
  }
}
return 0;
}

补充：软件开发 , C++ ,