如果看不懂的话，这是种类并查集的做法网上搜一下。
#include <stdio.h>
#define MAXN 100001
int parent[MAXN];
int relation[MAXN];
int count[MAXN];
bool flag[MAXN];
void Initial(int N)
{	for(int i=0;i<=N;++i)
		parent[i]=i,relation[i]=0,flag[i]=false,count[i]=1;
}
int FindRoot(int x)
{	if(x!=parent[x])
	{	int temp=parent[x];
		parent[x]=FindRoot(parent[x]);
		relation[x]=(relation[x]+relation[temp])%2;
	}
	return parent[x];
}
void Union(int i,int j)
{	int x=FindRoot(i),y=FindRoot(j);
	if(x==y)	return;
	if(count[x]>=count[y])
	{	parent[y]=x;
		count[x]+=parent[y];
		relation[y]=(relation[i]+relation[j]-1)%2;
	}
	else
	{	parent[x]=y;
		count[y]+=parent[x];
		relation[x]=(relation[i]+relation[j]-1)%2;
	}
}
int main()
{	int T;
	int N,M,i,a,b,x,y;
	char c;
	scanf("%d",&T);
	while(T--)
	{	scanf("%d %d",&N,&M);
		Initial(N);
		while(M--)
		{	scanf(" %c %d %d",&c,&a,&b);
			flag[a]=flag[b]=true;
			if(c=='D')
				Union(a,b);
			else if(c=='A')
			{	if(flag[a]==false||flag[b]==false)
					puts("Not sure yet.");
				else
				{	x=FindRoot(a),y=FindRoot(b);
					if(x!=y)	puts("Not sure yet.");
					else
					{	if(relation[a]==relation[b])
							puts("In the same gang.");
						else
							puts("In different gangs.");
					}
				}
			}
		}
	}
	return 0;
}