poj2492A Bug's Life——带权并查集

题目：http://poj.org/problem?id=2492

所有元素加入同一个并查集中，通过其偏移量%2将其分类为同性与异性，据此判断事件。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int p,n,m,fa[2005],d[2005];
bool flag;
int find(int x)
{
if(fa[x]==x)return x;
else
{
int root=find(fa[x]);
d[x]+=d[fa[x]];
fa[x]=root;
}
return fa[x];
}
int main()
{
scanf("%d",&p);
for(int g=1;g<=p;g++)
{
scanf("%d%d",&n,&m);
int a,b;
flag=0;
//memset(fa,0,sizeof fa);
for(int i=1;i<=n;i++)fa[i]=i;
memset(d,0,sizeof d);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if(flag)continue;
int u=find(a),v=find(b);
if(u==v)
if((d[a]-d[b])%2==0)flag=1;//同性
if(u!=v)
{
//du+da=db+1;
fa[u]=v;
d[u]=d[b]-d[a]+1;
}
}
if(flag)printf("Scenario #%d:\nSuspicious bugs found!\n\n",g);
else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",g);
}
}