题目的意思是：在一个城市，有两个犯罪团伙。输入N（人的个数）和M（信息的个数）。后面M条信息是一个字母加上两个数字i和j，如果字母为D，则说明i和j属于不同的犯罪团伙，如果字母是A，则要你判断i和j的关系，属于同一个还是属于不同的还是不确定。
一开始，觉得这个题目计较棘手，属于D的情况下，是属于不同的犯罪团伙，不知道如何来解决。
后来想到了之前看到的一题，POJ1182食物链，判断有多少条信息是错的。有三个并查集来判断动物的关系。
所以这一题，我们可以用两个并查集来判断。N最大为10^5，所以并查集要开到2 * 10 ^ 5。i + N，表示 i 属于团伙N。这样就好解决了。
下面是AC的代码：
#include <iostream>#include <cstdio>using namespace std;const int MAX = 100005 * 2;int par[MAX];int N, M;int finds(int x)//并查集查找函数{if(x == par[x])return x;elsereturn par[x] = finds(par[x]);}void join(int x, int y)//并查集合并函数{x = finds(x);y = finds(y);if(x != y)par[y] = x;}int same(int x, int y)//判断是否是一个并查集{return finds(x) == finds(y);}int main(){int i, t, a, b;char str;scanf("%d", &t);while(t–){scanf("%d%d", &N, &M);getchar();for(i = 0; i <= MAX; i++) //初始化并查集par[i] = i;for(i = 0; i < M; i++){scanf("%c %d %d", &str, &a, &b);getchar();if(str == 'A')//输出信息{if(same(a, b))//属于同一个printf("In the same gang.\n");else if(same(a, b + N)) //属于不同的printf("In different gangs.\n");else//不确定的printf("Not sure yet.\n");}else{join(a, b + N);//因为是不属于同一个，，a与b + N属于同一个团伙join(a + N, b);//a + N 跟b属于一个团伙}}}return 0;}
『 不可能 』只存在於蠢人的字典里
