POJ 1703 Find them, Catch them .

题目地址

#include<iostream>
#include<cstdio>
#include<queue>
#include<map> 
#include<vector>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000+5;
int p[maxn],r[maxn];
int getParent(int x){if(p[x]==x) return x;int xp=getParent(p[x]);r[x]=(r[x]+r[p[x]])%2;return p[x]=xp;
}void merge(int xp,int yp,int x,int y)
{p[xp]=yp;r[xp]=(r[x]+r[y]+1)%2;
}
int main()
{int n,m,kase=0;int T;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) p[i]=i,r[i]=0;int x,y,xp,yp;char cmd; while(m--){cin>>cmd>>x>>y;xp=getParent(x);yp=getParent(y);if(cmd=='D'){if(xp!=yp) merge(xp,yp,x,y);}else {if(xp==yp&&r[x]==r[y]) cout<<"In the same gang.";else if(xp==yp&&r[x]!=r[y]) cout<<"In different gangs.";else cout<<"Not sure yet.";cout<<endl;}}}return 0;
}