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;
}