题意：给出T个测试样例
N个人 M组数据
A表示查询，D表示增加关系
#include <iostream> #include <stdio.h> using namespace std; int father[100050]; int relation[100050]; void init(int n) { for(int i=1;i<=n;i++) { father[i]=i; relation[i]=0; } } int find(int x) { if(x!=father[x]) { int tmp=father[x]; father[x]=find(tmp); relation[x]=(relation[x]+relation[tmp])%2; } return father[x]; } void Union(int x,int y) { int root1=find(x); int root2=find(y); father[root2]=root1; relation[root2]=(-relation[y]+1+relation[x])%2; } int main() { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; init(n); while(m--) { char s[5]; int x,y; scanf("%s",s); scanf("%d%d",&x,&y); if(s[0]=='D') { Union(x,y); } else { int fa,fb; fa=find(x); fb=find(y); if(fa!=fb) { printf("Not sure yet.\n"); } else { if(relation[x]==relation[y]) { printf("In the same gang.\n"); } else { printf("In different gangs.\n"); } } } } } return 0; }
