/*
题目大意：有两个不同的黑帮，开始的时候不清楚每个人是属于哪个的！
执行两个操作
A a, b回答a, b两个人是否在同一帮派，或者不确定
D a, b表示a, b两个人不在同一个帮派
思路：利用并查集将相同帮派的人合并到一起！
a ,b 不在同一个城市，那么 a, 和mark[b]就在同一个城市，
b 和 mark[a]就在同一个城市！
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define M 100005
using namespace std;
int f[M];
int mark[M];//mark[i]表示 i 与 mark[i]不在同一个黑帮
int rank[M];//为不同的集合的父亲节点记录其孩子机节点个数，在合并集合的时候，将
int n, m; //rank 值小的集合连接到 rank 值大的集合上去！ 这样在路径压缩的时候省去不少时间
void init(){
memset(mark, 0, sizeof(int)*(n+1));
memset(rank, 0, sizeof(int)*(n+1));
for(int i=1; i<=n; ++i)
f[i]=i;
}
int getFather(int x){
return x==f[x] ? x : f[x]=getFather(f[x]);
}
void Union(int a, int b){
int fa=getFather(a), fb=getFather(b);
if(fa!=fb){
if(rank[fa]>rank[fb]){
f[fb]=fa;
rank[fa]+=rank[fb]+1;
}
else{
f[fa]=fb;
rank[fb]+=rank[fa]+1;
}
}
}
int main(){
int t;
char cmd[3];
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
init();
while(m--){
int u, v;
scanf("%s%d%d", cmd, &u, &v);
if(cmd[0]=='A'){
int fu=getFather(u), fv=getFather(v);
if(fu==fv)
printf("In the same gang.\n");
else if(fu==getFather(mark[v]))
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
}
else{
if(!mark[u] && !mark[v]){
mark[u]=v;
mark[v]=u;
}
else if(!mark[u]){
mark[u]=v;
Union(u, mark[v]);
}
else if(!mark[v]){
mark[v]=u;
Union(v, mark[u]);
}
else {
Union(u, mark[v]);
Union(v, mark[u]);
}
}
}
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3892571.html，如需转载请自行联系原作者
