并查集——poj2492（带权并查集入门）

一、题目回顾

题目链接：传送门

题意：给定n只虫子，不同性别的可以在一起，相同性别的不能在一起。给你m对虫子，判断中间有没有同性别在一起的。

二、解题思路

种类并查集
和poj1073的本质一样
详见poj1073题解

大概思路：每得到一对虫子就判断下他们是否在同一个集合，并且他们的性别是否相同，如果相同则有同性恋，后面就算输入数据也不用做处理了，否则就一直处理下去。

三、代码

#include<cstdio>

#include<iostream>

using namespace std;

const int maxn = 100000+10;

int pre[maxn]; 		//存父亲节点

int r[maxn]; 		//存与根节点的关系，0 代表同类， 1代表不同类

int T,n,m;

void init()

{

	for(int i=1;i<=n;i++){

		pre[i] = i;

		r[i] = 0;

	}

}

int find(int x)

{

	if(x == pre[x])	return x;

	int t = pre[x];

	pre[x] = find(pre[x]);

	r[x] = (r[x]+r[t])%2;

	return pre[x];

}

void unite(int x,int y)

{

	int fx = find(x);

	int fy = find(y);

	pre[fx] = fy;

	r[fx] = (r[x]+1+r[y])%2;

}

int main()

{

	scanf("%d",&T);

	int kase = 1;

	while(T--){

		scanf("%d%d",&n,&m);

		init();

		int a,b,flag=0;

		while(m--){

			scanf("%d%d",&a,&b);

			if(find(a)==find(b)){

				if(r[a]==r[b]){

					flag = 1;

				}

			}

			else{

				unite(a,b);

			}

		}

		printf("Scenario #%d:\n",kase++);

		if(flag==1)	printf("Suspicious bugs found!\n\n");

		else	printf("No suspicious bugs found!\n\n");

	}

	return 0;

}

巴特西

并查集——poj2492（带权并查集入门）

最新文章

热门文章