刚开始以为是最基本的并查集，无限超时。
这个特殊之处，就是可能有多个集合。
比如输入D 1 2 D 3 4 D 5 6...这就至少有3个集合了。并且任意2个集合之间成员的敌我关系不明。
这里每个集合里面的成员关系要记录，他们在一个集合里，只是因为他们关系明确，敌人或者朋友。
千万不要简单的认为成朋友在一个集合，敌人在另外一个集合，分成2个集合。因为题目说只有2个匪帮，很容易进入这个误区。
我们只要记录一个成员和自己父亲的敌我关系和建树就可以了。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int MM = ;
int father[MM];
int relation[MM]; int find(int x)
{
if(x == father[x]) return x;
int r = find(father[x]);
relation[x] ^= relation[father[x]];
return father[x] = r;
} void join(int x, int y)
{
int fx = find(x);
int fy = find(y); father[fx] = fy;
if(relation[y] == )
relation[fx] = relation[x];
else
relation[fx] = - relation[x];
} void solve()
{
int T,N,M,i,a,b,ta,tb;
char str;
scanf("%d", &T);
while(T--)
{
scanf("%d %d",&N, &M); for(i = ; i <= N; ++i)
{
father[i] = i;
relation[i] = ;
} for(i = ; i < M; ++i)
{
getchar();
scanf("%c %d %d", &str, &a, &b);
if(str == 'D')
join(a, b);
else
{
ta = find(a);
tb = find(b);
if(ta == tb)
{
if(relation[a] == relation[b])
printf("In the same gang.\n");
else
printf("In different gangs.\n");
}
else
printf("Not sure yet.\n");
}
}
}
} int main()
{
solve();
return ;
}