<题目链接>
题目大意：
已知所有元素要么属于第一个集合，要么属于第二个集合，给出两种操作。第一种是D a b，表示a,b两个元素不在一个集合里面。第二种操作是A a b，表示询问a,b两个元素是否在同一个集合里面。如果不能确定的话打印not sure。否则给出答案。
解题分析：
典型的带权并查集，通过点与根节点的关系来判断它们是否属于同一阵营，而点与根节点的关系又是在状态压缩时，通过它与父亲节点的关系来更新。
#include <cstdio>
#include <cstring> const int maxn=+; int n,m;
struct node{
int pa; //父亲节点
int dis; //与根节点的关系
}arr[maxn]; void init(){
for(int i=;i<=n;i++){
arr[i].pa=i;
arr[i].dis=;
}
} int find(int x){
if(arr[x].pa==x)
return x;
int temp=arr[x].pa;
arr[x].pa=find(arr[x].pa);
arr[x].dis=(arr[x].dis+arr[temp].dis+)%; //n现在与根节点的关系为原来与根节点(父亲节点)的关系加上父亲节点与根节点的关系
return arr[x].pa;
} void uion(int a,int b){
int ra=find(a);
int rb=find(b);
arr[ra].pa=rb;
arr[ra].dis=(-arr[a].dis+arr[b].dis+)%; //运用矢量去计算ra到rb的距离
} int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
init();
for(int i=;i<=m;i++){
getchar();
char ch;
int a,b;
scanf("%c %d %d",&ch,&a,&b);
if(ch=='A'){
int ra=find(a);
int rb=find(b);
if(ra!=rb){
printf("Not sure yet.\n");
}
else{
if(arr[a].dis!=arr[b].dis){
printf("In different gangs.\n");
}
else{
printf("In the same gang.\n");
}
}
}
else{
uion(a,b); //将a,b的关系连接起来
}
}
}
return ;
}
2018-08-20