Find them, Catch them

Time Limit: 1000MS Memory Limit: 10000K

Description

The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)

Assume N (N <= 105) criminals are currently in Tadu City, numbered from 1 to N. And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake. You will be given M (M <= 105) messages in sequence, which are in the following two kinds:

  1. D [a] [b]
    where [a] and [b] are the numbers of two criminals, and they belong to different gangs.

  2. A [a] [b]
    where [a] and [b] are the numbers of two criminals. This requires you to decide whether a and b belong to a same gang.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. Each test case begins with a line with two integers N and M, followed by M lines each containing one message as described above.

Output

For each message “A [a] [b]” in each case, your program should give the judgment based on the information got before. The answers might be one of “In the same gang.”, “In different gangs.” and “Not sure yet.”

Sample Input

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

Sample Output

Not sure yet.
In different gangs.
In the same gang.

第一种做法（比较难懂）

思路

设两个数组一个是判断是否知道两个团伙的关系，一个是判断是否同一个团伙或者不同团伙，father数组就是将出现的人不断构成联系，rank就是判断这两个是否是敌对，然后就是两个自定义函数才是关键：
1 不断递归然后从根结点开始判断同一团伙，每次都是和父节点判断，但是父节点往上到最后就是根结点了，所以父节点的比较和根结点是有联系的，也可以把父节点当作根结点，所以子结点和父节点一样的话，那么就是子节点和根结点是一样 的，就是1，反之就是0了。
2 就是合并的自定义函数了，首先，就是看是否已经在一个集合里面了，然后进行比较是否是同一个犯罪团伙，是的话子结点就是1，不是的话就是0.

#include <iostream>
using namespace std;
int father[100010], rankn[100010];
int findfather(int x) {
	if (x != father[x]) {
		int temp = father[x];
		father[x] = findfather(father[x]);
		if (rankn[x] == rankn[temp]) rankn[x] = 1;
		else rankn[x] = 0;
	}
	return father[x];
}
void unionfather(int a, int b) {
	int fa = findfather(a);
	int fb = findfather(b);
	if (fa != fb) {
		father[fa] = fb;
		if (rankn[a] == rankn[b]) rankn[fa] = 0;
		else rankn[fa] = 1;
	}
}
int main() {
	int t, n, m;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= n; i++) {
			rankn[i] = 1;
			father[i] = i;
		}
		while (m--) {
			char s;
			int x, y;
			getchar();
			scanf("%c %d %d", &s, &x, &y);
			if (s == 'D') unionfather(x, y);
			else {
				int fx = findfather(x);
				int fy = findfather(y);
				if (fx != fy) printf("Not sure yet.\n");
				else if (rankn[x] == rankn[y]) printf("In the same gang.\n");
				else printf("In different gangs.\n");
			}
		}
	}
	return 0;
}

第二种做法

思路：

种类并查集的思路，还是先套并查集模板，然后a与b+n，b+n与a合并，这里的超过n是作为一个中间连接的作用，因为a和b是对立的，所以必能直接合并，但是多了这个中间连接的实际上对于a和b的关系是不影响的，举个例子，题目中1 2合并的时候就是1 7和6 2，当2 4时就是7 4，2 9，这样1和4就合并到了同一个集合里面了。

#include <iostream>
using namespace std;
const int maxn = 200020;
int father[maxn];
int findfather(int x) {
	int a = x;
	while (x != father[x]) x = father[x];
	while (a != father[a]) {
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;
}
void unionfather(int a, int b) {
	int fa = findfather(a);
	int fb = findfather(b);
	if (fa != fb) father[fa] = fb;
}
int main() {
	int t, n, m;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= 2 * n; i++) father[i] = i;
		while (m--) {
			getchar();
			char c;
			int a, b;
			scanf("%c %d %d", &c, &a, &b);
			if (c == 'D') {
				unionfather(a, b + n);
				unionfather(a + n, b);
			} else {
				int fa = findfather(a);
				int fb = findfather(b);
				int ffb = findfather(b + n);
				if (fa == fb) printf("In the same gang.\n");
				else if (fa == ffb) printf("In different gangs.\n");
				else printf("Not sure yet.\n");
			}
		}
	}
	return 0;
}