这道题与食物链那一道题是同一类型的，但稍微简单些
比普通的并查集多了一个relation [i]数组，记录与父亲节点的关系，在并查集里的元素都是已经它们之间的关系的，在路径压缩与集合合并时不断的更新relation数组
r[i]=0代表与父节点同类，r[i]=1代表异类，初始化为同类
下面推导如何在路径压缩时更新关系：
根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系
枚举出来所有情况，找出规律(r1+r2)%2或者 r1==r2? 0:1
（a, b） (b, c) (a, c) (r1+r2)%2 0 0 0 0 a 和 b是同类 ， b 和 c 是同类， 所以 a 和 c 也是同类 0 1 1 1 a 和 b是同类 ， b 和 c 是异类， 所以 a 和 c 也是异类 1 0 1 1 a 和 b是异类 ， b 和 c 是同类， 所以 a 和 c 是异类 1 1 0 0 a 和 b是异类 ， b 和 c 是异类， 所以 a 和 c 是同类 在集合合并时也可以枚举，同样用矢量运算也可以求得 #include<stdio.h> const int MAXN=100005; int pre[MAXN],re[MAXN]; int n,m; int ans; void init() { for(int i=1;i<=n;i++){ pre[i]=i; re[i]=0;//初始时父节点为本身，当然同类，初始为0 } } int find(int x) //找根节点 { if(x!=pre[x]){ int t=pre[x]; //记录下父亲节点，方便以下更新 pre[x]=find(pre[x]);//根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系 r[x] = (r[x]+r[t])%2; ; } return pre[x]; } void merge(int x,int y) { //找到x与y的根节点 int fx=find(x); int fy=find(y); if(fx!=fy){ pre[fy]=fx;//合并 r[fx] = (r[x]+1+r[y])%2;// //fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系 } } int main(void) { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); char op[2]; int x,y; init(); while(m--){ scanf("%s%d%d",op,&x,&y); if(op[0]=='A') { if(find(x)!=find(y)){//不在同一棵树里，所以不确定 printf("Not sure yet.\n"); continue; } if(re[x]==re[y]) printf("In the same gang.\n"); else printf("In different gangs.\n"); } else merge(x,y); } } return 0; }