POJ2492 （并查集）

POJ2492 （并查集）

题目：假设昆虫之间是异性互动，给出昆虫的互动情况，判断假设是否成立；

输入：第一行t表示n个测试用例，每个测试用例第一行n，m表示n只昆虫，从1连续编号，m组互动情况；

输出：假设不成立：Suspicious bugs found!
假设成立：No suspicious bugs found!
题解：参考POJ1611

#include <cstdio>
#include <cstring>
#define maxn 4005
int s[maxn];
void init(){
	for(int i = 0;i < maxn;i++){
		s[i] = i;
	}
}
int find(int x){
	int r = x;
	while(r != s[r]) r = s[r];
	int i = x, j;
	while(i != r){
		j = s[i];
		s[i] = r;
		i = j;
	}
	return r;
}
void uni(int x, int y){
	int xx = find(x), yy = find(y);
	if(xx != yy) s[xx] = yy;
}
int main() {
	int t,n,m,x,y;
	scanf("%d", &t);
	for(int k = 1;k <=t ;k++){
		init();
		scanf("%d%d", &n,&m);
		bool ok = true;
		for(int i = 0;i < m;i++){
			scanf("%d%d", &x, &y);
			if(find(x) == find(y)) ok = false;
			uni(x, y + n);
			uni(x + n, y);
		}
		printf("Scenario #%d:\n", k);
		if(ok) printf("No suspicious bugs found!\n");
		else printf("Suspicious bugs found!\n");
		if(k != t) printf("\n");
	}
	return 0;
}