题目：http://poj.org/problem?id=1182
为每个动物创建三个元素i-A，i-B，i-C，并利用这3*N个元素建立并查集。
参考挑战程序设计书
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define maxn 100009 int N, K; int par[maxn*3], rankx[maxn*3]; int T[maxn], X[maxn], Y[maxn]; void init(int n) { for(int i=0;i<n;i++) { par[i]=i; rankx[i]=0; } } int find(int x){ if(par[x]==x) return x; else{ return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return ; if(rankx[x] < rankx[y]) { par[x]=y; }else{ par[y]=x; if(rankx[x]==rankx[y]) rankx[x]++; } } bool same(int x, int y) { return find(x)==find(y); } int main() { scanf("%d%d", &N,&K); init(N*3); int ans=0, x, y, t; for(int i=0;i<K;i++) { scanf("%d %d %d", &T[i],&X[i], &Y[i]); int t = T[i]; int x = X[i] - 1, y = Y[i] - 1; if(x <0 ||N <= x || y <0||N<=y){ ans++; continue; } if(t==1) { if(same(x, y + N)||same(x, y+2*N)){ ans++; } else { unite(x, y); unite(x+N, y+N); unite(x+N*2, y+N*2); } } else { if(same(x, y) || same(x, y + 2 *N)){ ans++; } else { unite(x, y+N); unite(x+N, y+2*N); unite(x+2*N, y); } } } printf("%d\n", ans); return 0; }