应用挑战程序设计那本书上的话：
对于每只动物i创建3个元素i—A，i—B，i—C，并用3xN个元素建立并查集。这个并查集维护如下信息：
（1）i—x表示“i属于种类x”
（2）并查集里的每一个组表示组内所有元素代表的情况都相同都同时发生或不发生
for example，如果i—A和j—B在同一个组里，就表示如果i属于种类A那么j一定属于种类B，如果j属于种类B那么i一定属于种类A。因此，对于每一条信息，只需要按照以下进行操作就可以了。
第一种，x和y属于同一类......合并x—A和y—A，x—B和y—B，x—C和y—C。
第二种，x吃y....................合并x—A和y—B，x—B和y—C，x—C和y—A。
不过在合并之前，需要先判断合并是否产生矛盾。例如在第一种信息的情况下，需要检查比如x—A和y—B或者y—C是否在同一组等信息
#include<cstdio>
#include<cstring>
const int N=50000+10;
int pre[N*3];
void init(int n)
{
for(int i=0;i<=n*3;++i)
pre[i]=i;
}
int find(int x)
{
if(x==pre[x])
return x;
else
return pre[x]=find(pre[x]);
}
bool same(int a,int b)
{
return find(a)==find(b);
}
void un(int a,int b)
{
int x=find(a);
int y=find(b);
if(x==y)
return;
else
pre[x]=y;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int ans=0;
init(n);
for(int i=0;i<k;++i){
int r,x,y;
scanf("%d%d%d",&r,&x,&y);
if(x>n||y>n||x<=0||y<=0){
++ans;
continue;
}
if(r==1){
if(same(x,y+n)||same(x,y+2*n))
++ans;
else{
un(x,y);
un(x+n,y+n);
un(x+2*n,y+2*n);
}
}
else{
if(same(x,y)||same(x,y+2*n))
++ans;
else{
un(x,y+n);
un(x+n,y+2*n);
un(x+2*n,y);
}
}
}
printf("%d
",ans);
return 0;
}
接下来应用这种思路写POJ的2492
题意：就是说有N个虫子，异性交配，但现在不知道虫子的性别，现在给出M个事件，问会不会出现同性交配的现象
思路：创建两个组，维护（x，y+n），（y，x+n）
#include<cstdio>
#include<cstring>
#include<cmath>
const int qq=2000+5;
int pre[qq*2];
void init(int n)
{
for(int i=0;i<=n*2;++i)
pre[i]=i;
}
int find(int x)
{
if(x==pre[x])
return x;
else
return pre[x]=find(pre[x]);
}
bool same(int a,int b)
{
return find(a)==find(b);
}
void un(int a,int b)
{
int x=find(a);
int y=find(b);
if(x==y)
return;
else
pre[x]=y;
}
int main()
{
int t;scanf("%d",&t);
int p=1;
while(t--){
printf("Scenario #%d:
",p++);
int x,y,n,k;
scanf("%d%d",&n,&k);
init(n);
int flag=1;
for(int i=0;i<k;++i){
scanf("%d%d",&x,&y);
if(same(x,y)||same(y,x))
flag=0;
else{
if(flag){
un(x,y+n);
un(y,x+n);
}
}
}
if(flag)
printf("No suspicious bugs found!
");
else
printf("Suspicious bugs found!
");
if(t) printf("
");
}
return 0;
}
POJ上刷题留心，题目如何给你一定要按照它的做，比如他只有一组数据输入，你别while(scanf("")!=EOF) 我就以为这样纠结了一个下午，
总之刷POJ一定要多留心，要多相信自己的代码，剩下的可能就是题目细节方面的错误了