Find them, Catch them（poj 1703）
题目大意：
在这个城市里有两个黑帮团伙，现在给出N个人，问任意两个人他们是否在同一个团伙
输入D x y代表x于y不在一个团伙里
输入A x y要输出x与y是否在同一团伙或者不确定他们在同一个团伙里
思路：并查集
#include<cstdio> #include<iostream> #include<cstring> #define M 100010 using namespace std; int fa[M*2]; int find(int x) { if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void init() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=2*n;i++) fa[i]=i; for(int i=1;i<=m;i++) { char c; int x,y; cin>>c; scanf("%d%d",&x,&y); int a=find(x),b=find(y); int aa=find(x+n),bb=find(y+n); if(c=='A') { if(a==b)printf("In the same gang. "); else if(a==bb||b==aa)printf("In different gangs. "); else printf("Not sure yet. "); } else { fa[aa]=b; fa[bb]=a; } } } int main() { int T; scanf("%d",&T); while(T--) { memset(fa,0,sizeof(fa)); init(); } return 0; }