A bug‘s life 虫子的生活(带权并查集)

题目链接: 2492 -- A Bug's Life (poj.org)

题目描述:

思路: 带权并查集，处理方法基本与食物链(http://t.csdnimg.cn/fSnRr)相同，没什么思维创新

但是一开始WA了几次，有些细节没有注意好，还是需要静下心来，好好分析问题，需要警惕！

参考代码:

//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2010;
int fa[N];
int dis[N];
int t,n,m;
void init(){for(int i=1;i<=n;i++){fa[i]=i;dis[i]=0;}return ;
}int finds(int x){if(fa[x]==x) return x;int res=finds(fa[x]);dis[x]+=dis[fa[x]];dis[x]%=2;fa[x]=res;return res;
}void unions(int x,int y){int u=finds(x);int v=finds(y);if(u==v) return ;fa[u]=v;dis[u]=1+dis[x]+dis[y];dis[u]%=2;return ;
}int main(void){scanf("%d",&t);int g=0;while(t--){scanf("%d%d",&n,&m);init();g++;printf("Scenario #%d:\n",g);int flag=0;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);if(flag) continue;int u=finds(x);int v=finds(y);if(u==v){int res=(dis[x]+dis[y]+2)%2;if(res!=1) flag=1;}else unions(x,y);}if(flag){printf("Suspicious bugs found!\n");}else printf("No suspicious bugs found!\n");if(t) printf("\n");}return 0;
}