问题传送门：

题意：

两个犯罪团伙：一个帮派至少有一人。
有N个罪犯，编号从1 至 N （N<=100000）。不知道具体属于哪一个团伙。
有M（M<=100000）次操作。
D a b 表示a、b是不同帮派
A a b 询问a、b关系

第一行是数据总数 T (1 <= T <= 20)
每组数据第一行是N、M，接下来M行是操作
对于每一个A操作，回答：
"In the same gang."
"In different gangs."
"Not sure yet."

分析：

是最简单的带权值并查集，和poj1182很像，

poj1182

只要理解了1182这个题，那么这一题就简单了。
权值记录了集合中每个节点之间的关系。
这一题只有两种关系，同帮派，不同帮派。
可以分别用数字        0     1   表示这两种关系。
然后还是利用路径压缩的过程计算出每个节点个根节点的关系。
公式和1182一样，
通过根节点可以计算集合中任意两个节点之间的关系。

这样一来，对于每一次询问A操作，计算他们的关系判断是不是 0 .
对于每一次 D 操作，把 a , b 加入集合，并且跟新集合中的关系。
这一点和1182也一样。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 1e5+10;
int r[MAXN];
int rel[MAXN];

void init(int n)
{
	for (int i = 1; i <= n; i++){
		r[i] = i; rel[i] = 0;
	}
}

int Find(int x)
{
	if (x == r[x])
		return r[x];
	else
	{
		int t = r[x];
		r[x] = Find(r[x]);
		rel[x] = (rel[x]+rel[t]) % 2;
		return r[x];
	}
}
void Join(int a, int b)
{
	int ra = Find(a);
	int rb = Find(b);
	if (ra != rb)
	{
		r[ra] = rb;
		rel[ra] = (1+rel[b]-rel[a]+2)%2;
	}
}

int main()
{
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	char c[2];
	int T, n ,m, a, b, f;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		init(n);
		for (int i = 0; i < m; i++)
		{
			scanf("%s %d %d", &c, &a, &b);
			if (c[0] == 'D') {
				Join(a, b);
			} else {
				
				if (Find(a)==Find(b)&&(rel[a]-rel[b]+2)%2==0)
					cout << "In the same gang." << endl;
				else if (Find(a)==Find(b))
					cout << "In different gangs." << endl;
				else 
					cout << "Not sure yet." << endl;
			}
		}
	}
	return 0;
}