#include <iostream>
using namespace std;


const int MAXN = 100001;

class UFset
{
public:
	int parent[MAXN];
	UFset();
	int Find(int);
	void Union(int, int);
};

UFset::UFset()
{
	for (int i=0; i<MAXN; i++)
		parent[i] = -100002;
	//memset(parent, -100002, sizeof(parent));
}

int UFset::Find(int x)
{
	if (parent[x] < 0)
		return x;
	else
		parent[x] = Find(parent[x]); // 压缩路径
}

void UFset::Union(int x, int y)
{
	int pX = Find(x);
	int pY = Find(y);
	int tmp;
	if (pX != pY)
	{
		tmp = parent[pX] + parent[pY]; // 加权合并
		if (parent[pX] > parent[pY])
		{
			parent[pX] = pY;
			parent[pY] = tmp;
		}
		else
		{
			parent[pY] = pX;
			parent[pX] = tmp;
		}
	}
}

int main()
{
	int caseTime;
	char t;
	int tmp, m;
	int x, y;
	int px, py;
	//scanf("%d\n", &caseTime);
	cin >> caseTime;
//	scanf("%d", &caseTime);
	while (caseTime-- != 0)
	{
		UFset diff;
		UFset same;
	//	scanf("%d ", &tmp);
	//	scanf("%d\n", &m);
		cin >> tmp >> m;
		for (int i=0; i<m; i++)
		{
		/*	scanf("%c ", &t);
			scanf("%d ", &x);
			scanf("%d\n", &y);*/
		//	scanf("%c %d %d", &t, &x, &y);
		//	printf("%c %d %d\n", t, x, y);
			cin >> t >> x >> y;
			
			if (t == 'A')
			{
				if (same.Find(x) == same.Find(y))
				{
					printf("In the same gang.\n");
				}
				else if (diff.Find(x) == diff.Find(y))
				{
					printf("In different gangs.\n");
				}
				else
				{
					printf("Not sure yet.\n");
				}
			}
			else
			{
				if (diff.parent[x] == -100002 && diff.parent[y] == -100002)
				{
					diff.Union(x, y);
					if (diff.Find(x) == x) 
						diff.parent[x] = -y;
					else 
						diff.parent[y] = -x;
				}
				else
				{
					px = diff.Find(x);
					py = diff.Find(y);
					if (diff.parent[px] != -100002)
					{
						if (px != x)
							same.Union(px, y);
						else
							same.Union(-diff.parent[px], y);
					}
					if (diff.parent[py] != -100002)
					{
						if (py != y)
							same.Union(py, x);
						else
							same.Union(-diff.parent[py], x);
					}
				}
		
			}
		}
	}
	return 0;
}

• 同tn同学的方法过了, 不过还是不知道原来的怎么会re..-_- (2377) qywyh_scut 2006-08-19 00:54:01