这个题目一看就是用并查集，有N个国家代表，在M行给出两两之间的关系，敌人或者朋友，（当然如果该关系跟已知关系冲突，则输出-1）
关系的几个约束条件时这样的
在朋友方面，朋友的朋友就是自己的朋友，这个就是并查集。
在敌人方面，
x和其所有朋友的敌人都是敌人。
x和其所有敌人的敌人都是朋友。
主要是这个敌人的状态不太好表示，不是一个并查集能做到的，我一开始犯糊涂，直接用个图把x的敌人存贮起来，但是因为每次交新的朋友或者敌人，就要搜索全图，而且要把自己的敌人圈更新到整个朋友圈，这样不仅难以实现，复杂度也是相当高
后来就发现一个神级方法，简单易用，即，每个国家都有自己的对立面（实际上不存在），作用是这样的，x的对立面为x+n，如果某国y要跟x做敌人，则，y就和x+n放在同一个并查集里。这样就不会跟本体有影响，但是又达到了结仇的目的。
这样的话，x和y结盟，则 x和y属于一个集合， x+n和y+n属于同一集合（把对立面也绑定，再结仇的时候无论是和x还是y结仇，都会同时跟两个国家结仇，这样就其实就达到了第一个条件）。
如果x和y结仇，则x和y+n在同一集合，同时，y和x+n在同一集合。（结仇之后，如果两个国家有共同的仇人，则通过并查集操作，必定到了同一个集合，这样就满足了仇人的仇人是朋友的条件）
这样判断前后是否冲突，也可以根据这几个条件，如果当前操作是结仇，则一旦发现x和y已经是一个集合（或者他们的对立面），则冲突
如果当前是结盟，一旦发现x和y+n是一个集合 或者 y和x+n是一个集合，则冲突。
#include <iostream> #include <cstdio> #define N 10010 using namespace std; int f[2*N]; int n,x,y,c; void init() { for (int i=0;i<=2*n;i++){ f[i]=i; } } int findset(int a) { if (a!=f[a]) f[a]=findset(f[a]); return f[a]; } void solve() { int r1,r2,r3,r4; r1=findset(x); r2=findset(y); r3=findset(x+n); r4=findset(y+n); //cout<<r1<<" "<<r2<<" "<<r3<<" "<<r4<<endl; if (c==1) { if (r1==r4){ puts("-1"); return; } f[r1]=r2; f[r3]=r4; return; } if (c==2) { if (r1==r2) { puts("-1"); return; } f[r1]=r4; f[r2]=r3; return; } if (c==3) { if (r1==r2) puts("1"); else puts("0"); } if(c==4) { if (r1==r4) puts("1"); else puts("0"); } } int main() { int i,j; scanf("%d",&n); init(); while (scanf("%d%d%d",&c,&x,&y)) { if (!c) break; solve(); } return 0; }