题意:有两个犯罪集团,现在有两种操作,D [a] [b]表示a和b是属于不同犯罪集团的,A [a] [b] 是询问你a和b的关系,如果ab属于同一个犯罪集团,输出In the same gang.    如果ab属于不同犯罪集团,输出In different gangs.    否则输出  Not sure yet.

思路:赤裸裸的种类并查集,0代表ab属于同一集团,1代表不同,要是不在同个树里面,就是不确定.......

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 100005
int father[M],rank[M];
int find(int x)
{
if(x==father[x])
return x;
int tmp=father[x];
father[x]=find(tmp);
rank[x]=(rank[x]+rank[tmp])%2;
return father[x];
}
void liantong(int x,int y)
{
int tmp=find(x);
int tmp1=find(y);
if(tmp!=tmp1)
{
father[tmp1]=tmp;
rank[tmp1]=(2-1+2-rank[y]+rank[x])%2;
} }
int main()
{
int text;
scanf("%d",&text);
while(text--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
father[i]=i;
rank[i]=0;
}
while(m--)
{
char ch[10];
int tmp,tmp1;
scanf("%s%d%d",ch,&tmp,&tmp1);
if(ch[0]=='D')
liantong(tmp,tmp1);
else
{
int x=find(tmp);
int y=find(tmp1);
if(x==y)
{
int r=(2-rank[tmp]+rank[tmp1])%2;
if(r==0)
printf("In the same gang.\n");
else
printf("In different gangs.\n");
}
else
printf("Not sure yet.\n");
}
}
}
return 0;
}
05-01 04:20