并查集经典题，但是太坑了，数据只有一组，用EOF读入无限WA,我就这么对着正确的代码查了半个多小时，次奥。
把一个结点拆成3个结点分别代表属于A,B,C三类，
对于X，Y同类，有如果XA->YA,XB->YB,XC->YC 所以直接把两两并起来，当然要判断能不能并
对于X吃Y ,有 XA->YB ,XB->YC , XC->YA ,同上
太坑了！！！！！！！！！！！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<vector> 9 #define maxn 50010 10 #define maxm 100010 11 using namespace std; 12 int father[maxn*3]; 13 int n,m; 14 int cmd[maxm],x[maxm],y[maxm]; 15 void init(){ 16 for(int i=0;i<maxn*3;++i){ 17 father[i]=i; 18 } 19 } 20 int Find(int x){ 21 return father[x]==x?x:father[x]=Find(father[x]); 22 } 23 void Union(int x,int y){ 24 x=Find(x); 25 y=Find(y); 26 if(x!=y)father[x]=y; 27 } 28 bool same(int x,int y){ 29 return Find(x)==Find(y); 30 } 31 void solve(){ 32 int ans =0; 33 init(); 34 for(int i=0;i<m;++i){ 35 int c = cmd[i]; 36 int xx = x[i]-1; 37 int yy = y[i]-1; 38 if(xx<0||xx>=n||yy<0||yy>=n){ 39 ans++; 40 continue; 41 } 42 else if(c==1){ 43 if(same(xx,yy+n)||same(xx,yy+2*n)||same(xx+n,yy)||same(xx+n,yy+2*n)||same(xx+2*n,yy)||same(xx+2*n,yy+n)){ 44 ans++; 45 continue; 46 } 47 else { 48 Union(xx,yy); 49 Union(xx+n,yy+n); 50 Union(xx+2*n,yy+2*n); 51 } 52 } 53 else{ 54 if(same(xx,yy)||same(xx,yy+2*n)||same(xx+n,yy)||same(xx+n,yy+n)||same(xx+2*n,yy+n)||same(xx+2*n,yy+2*n)){ 55 ans++; 56 continue; 57 } 58 else { 59 Union(xx,yy+n); 60 Union(xx+n,yy+2*n); 61 Union(xx+2*n,yy); 62 } 63 } 64 } 65 printf("%d ",ans); 66 } 67 int main (){ 68 scanf("%d%d",&n,&m); 69 for(int i=0;i<m;++i){ 70 scanf("%d%d%d",&cmd[i],&x[i],&y[i]); 71 } 72 solve(); 73 }