题意：给你t组数据，每组数据给你编号为1-n的坏人，这些坏人要么属于团伙A，要么属于团伙B，然后给你m次操作：

　　　A操作：询问x和y是不是同一个团伙

　　　D操作：告诉你x和y不是同一个团伙

 

思路：和POJ 1182 食物链是一样的。

 

AC代码：

#include 
     
      #include 
      
       using namespace std;const int MAX_N = 200005;int t,n,m,fa[MAX_N],x,y;char op[2];int find(int x){	if(x == fa[x]) return x;	else return fa[x] = find(fa[x]);}void unite(int x, int y){	x = find(x);	y = find(y);	if(x == y) return;	fa[x] = y;}bool same(int x, int y){	return find(x) == find(y);}void init(){	for(int i = 1; i <= n*2; i++)		fa[i] = i, opp[i] = 0;}void solve(){	while(m--)	{		scanf("%s %d %d", op, &x, &y);		if(op[0] == 'A')		{			if(same(x,y))				puts("In the same gang.");			else if(same(x,y+n))				puts("In different gangs.");			else puts("Not sure yet.");		}else		{			unite(x,y+n);			unite(x+n,y);		}	}}int main(){	scanf("%d", &t);	while(t--)	{		scanf("%d %d", &n, &m);		init();		solve();	}	return 0;}