其实是root[0]是并查集,root[1]是一个记录和自己不在同意集合的元素,每次记录D命令中自己的对立并且把本次对立加在上次对立所在的集合里面,如果getroot()值相同的话就是same,不同的话有俩种情况,一种就是a的对立和b在同一集合里面的话就是a和b different,如果不是的话就是not sure

#include <stdio.h>

int root[100009][2];

int getroot(int a)
{
	if(a==root[a][0])
		return a;
	else return root[a][0]=getroot(root[a][0]);
}
void tunion(int a,int b)
{
	if(getroot(a)==getroot(b))
		return;
	root[getroot(a)][0]=getroot(b);
}

void main()
{
	int m,n;
	int a,b,c,d,e,f;
	int x,y;
	char com;

	scanf("%d",&x);
	for(y=0;y<x;y++)
	{
		scanf("%d%d",&n,&m);
		for(a=1;a<=n;a++)
		{
			root[a][0]=a;
			root[a][1]=0;
		}

		for(a=0;a<m;a++)
		{
			scanf("\n%c%d%d",&com,&b,&c);
			if(com=='A')
			{
				if(b==c||getroot(b)==getroot(c))
					printf("In the same gang.\n");
				else
				{
					if(getroot(root[b][1])==getroot(c))
						printf("In different gangs.\n");
					else
						printf("Not sure yet.\n");
				}

			}

			else if(com=='D')
			{
				d=root[b][1];//第一个数的对立
				e=root[c][1];//第二个数的对立

				if(d)
					tunion(c,d);
				root[b][1]=c;
				if(e)
					tunion(b,e);
				root[c][1]=b;
			}
		}

	}

}