poj 抓小偷

抓小偷"/>

poj 抓小偷

类似食物链 比食物链简单

#include <stdio.h>
#define MAX 100010
int par[MAX];
int kin[MAX];
void Init(int n)
{	for (int i = 1;i <= n;i++){par[i] = i;kin[i] = 0;}
}
void Union(int xroot,int yroot,int x,int y){par[yroot] = xroot;kin[yroot] = ~(kin[x]^kin[y]);	
}
int Find(int x){if(par[x]==x)return x;int temp = par[x];par[x] = Find(temp);kin[x] = kin[x]^kin[temp];return par[x];
}
int main(){int n,k,t,x,y;char o;scanf("%d",&t);while(t--){scanf("%d%d\n",&n,&k);	Init(n);while (k--){scanf("%c %d %d\n",&o,&x,&y);int xroot = Find(x);int yroot = Find(y);if(o=='A'){if(n==2) printf("In different gangs.\n");else{if (xroot==yroot){if(kin[x]!=kin[y])printf("In different gangs.\n");elseprintf("In the same gang.\n");}else{	printf("Not sure yet.\n");}}}else{Union(xroot,yroot,x,y);}}}
}