并查集经典题目，详细写一下吧
题意：虽然比较长，但是题意还是比较好懂的。如果a和b是朋友，b和c是朋友，那么a和c是朋友。如果a和b是敌人，c和b是敌人，那么a和c要成为朋友
操作1和2是假设（或者说试图建立某种关系），如果能成立不用输出，并且保持这种关系，如果这种假设（关系）与之前已经存在的关系是冲突的，那么输出-1，并且要保持原来的关系，放弃当前这个失败的。操作3和4是判断，即根据当前已知的关系，判断某两个人之间的关系是否成立，成立输出1，不成立或者无法确定就输出0
1 a b 即试图让a和b成为朋友
唯一不成立是：a在b的敌对集合中（那么同时b一定在a的敌对集合中）
a和b有共同敌人，成立
a和b至少有一个没有敌人，成立
a和b都有敌人，但是敌人不同，也成立，不过要记得合并他们的敌人成为朋友
2 a b 即试图让a和b成为敌人
唯一不成立是：a和b在同一个集合
成立后要修改一些关系：a和b成了敌人，那么b归到a的敌对集合中，a归到b的敌对集合中
所以我们要用p数组来记录元素i处于那个集合（同集合的人都是朋友），还需要一个数组q去记录元素i的对立集合
其实我的代码写得不是太好，感觉有点罗嗦，但是想不到再怎么精简了
另外在查询祖先的时候，有压缩路径和没有压缩路径时间相差好大（0.048和0.580）
AC后找的一个博客，觉得他这样写挺好，比我的好理解多了，向他学习学习，哈哈，不过时间上貌似比我的慢，这就有点慢理解了，不过怎么说都好我还是推崇他的写法
http://hi.baidu.com/arosliu/item/d2933609055565354bc4a365
#include <cstdio> #include <cstring> #define N 10010 int p[N],q[N],m[N]; int n,a,b,pa,pb,qa,qb; int find(int x) { return x==p[x]?x:p[x]=find(p[x]); } void fun1() { if(pa==qb && pb==qa) printf("-1\n"); else { if(qa==-1 && qb==-1) p[pa]=pb; else if(qa==-1) p[pa]=pb; else if(qb==-1) p[pb]=pa; else { p[pa]=pb; p[qa]=qb; } } return ; } void fun2() { if(pa==pb) printf("-1\n"); else { q[pa]=pb; q[pb]=pa; if(qa!=-1) p[qa]=pb; if(qb!=-1) p[qb]=pa; } return ; } void fun3() { if(pa==pb) printf("1\n"); else printf("0\n"); return ; } void fun4() { if(pa==qb && pb==qa) printf("1\n"); else printf("0\n"); return ; } int main() { int c,a,b; scanf("%d",&n); for(int i=0; i<n; i++) { p[i]=i; m[i]=0; q[i]=-1;} while(scanf("%d%d%d",&c,&a,&b)) { if(!c && !a && !b) break; pa=find(a); //a元素所在集合是pa pb=find(b); //b元素所在集合是pb qa=q[pa]; if(qa!=-1)qa=find(qa); //集合pa的对立集合是qa qb=q[pb]; if(qb!=-1)qb=find(qb); //集合pb的对立集合是qb if(c==1) //建立朋友关系 fun1(); else if(c==2) //建立敌对关系 fun2(); else if(c==3) //判断朋友关系 fun3(); else //判断敌对关系 fun4(); } return 0; }