题目大意：在这个城市里有两个黑帮团伙，现在给出N个人，问任意两个人他们是否在同一个团伙，输入D x y代表x于y不在一个团伙里，输入A x y要输出x与y是否在同一团伙或者不确定他们在同一个团伙里。
解题思路：显示这道题仍然是要的并查集，而且也是用到加权，我们开个r数组
因为只存在两个状态 在同一个帮派，不再同一个帮派 给定的A x y 若他们的根节点不同那就无法判断他们的关系 若根节点相同且权值相同说明他们两在同一个帮派 根节点相同但权值不同说明他们两不在同一个帮派
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <map> #include <cmath> #include <queue> #include <string> #include <vector> using namespace std; #define sc(x) scanf("%d",&x) #define FOR(i,n) for(int i=1;i<=n;i++) #define pr(x) printf("%d\n",x) const int maxn=10e5+5; int p[maxn],r[maxn]; int n,m; char str[5]; void init()//初始化函数 { FOR(i,n) { p[i]=i; r[i]=0; } } int Find(int x) { if(x!=p[x]) { int k=Find(p[x]); r[x]=(r[x]+r[p[x]])%2; p[x]=k; } return p[x]; } void Unionset(int x,int y,int xx,int yy) { p[yy]=xx; r[yy]=(r[y]-r[x]+2+1)%2; } int main() { int t; sc(t); while(t--) { sc(n); sc(m); init(); FOR(i,m) { int x,y; scanf("%s %d %d",str,&x,&y); int xx=Find(x); int yy=Find(y); if(str[0]=='A') { if(xx!=yy)//根节点都不同无法判断关系 { puts("Not sure yet."); } else { if(r[x]==r[y])//权值相同 说明在同一个帮派 { puts("In the same gang."); } else { puts("In different gangs."); } } } else { Unionset(x,y,xx,yy); } } } return 0; }END！！！！！！！！！！！！！！！！
