Input
Output
Sample Input
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3
#include<iostream> #include<stdio.h> #define maxn 50005*3 using namespace std; int kind[maxn]; int rank[maxn]; void init() { for(int i=0;i<maxn;i++) kind[i]=i,rank[i]=0; } int findp(int x) { if(kind[x]==x) return x; else return kind[x]=findp(kind[x]); } void unit(int x,int y) { x=findp(x); y=findp(y); if(x==y) return; if(rank[x]<rank[y]) { kind[x]=y; } else { kind[y]=x; if(rank[x]==rank[y]) rank[x]++; } } bool same(int x,int y) { int ax=findp(x); int ay=findp(y); if(ax==ay) return true; else return false; } int main() { int n,k; int type,x,y; cin>>n>>k; init(); int ans=0; for(int i=0;i<k;i++) { scanf("%d%d%d",&type,&x,&y); if(x<0||x>n||y<0||y>n) { ans++; continue; } if(type==1) { if(same(x,y+n)||same(x,y+n+n)) { ans++; continue; } unit(x,y); unit(x+n,y+n); unit(x+2*n,y+2*n); } else { if(x==y) { ans++; continue; } if(same(x,y)||same(x,y+n+n)) { ans++; continue; } unit(x,y+n); unit(x+n,y+n+n); unit(x+n+n,y); } } printf("%d\n",ans); return 0; }
这道题之前做过，大神们用位运算+%3关系，当时搞明白了，不过又忘记了，重新做了一遍。思路来自：挑战程序竞赛。
我们维护三个关系：i-a,i-b,i-c。
分别表示i属于a,b,c.
如果x,y是同一物种，我们将（x-a,y-a）,（x-b,y-b）,（x-c,y-c）unit一下。
如果x吃y，则（x-a，y-b），（x-b，y-c），（x-c，y-a）unit
当然，在unit之前我们考虑一下是否为假话：
若同一物种：
假话的情况：x被y吃---》（x-a,y-b)
y被x吃--》（x-a，y-c）
若捕食关系x吃y，假话情况：
x，y同一物种：（x-a，y-a）
y吃x：（x-a，y-c）
这样利用并查集维护三个集合。最终ac。
原文：http://www.cnblogs.com/superxuezhazha/p/6361626.html
