POJ 1182 食物链 并查集

时间:2022-09-25 21:32:50

题意:有N只动物,分别编号1-N。所有动物都属于A、B、C中的其中一种。已知A吃B,B吃C,C吃A。按顺序给出K个信息

   第一种:x和y是同一种类;第二种,x吃y。求问这些信息中有多少个假信息?

 

思路:我是看《挑战程序设计竞赛》的。没想到并查集也可以维护两种关系。

   题目中,有捕猎关系和“同一种”关系。

   可以通过给每个动物i创建3个元素x-A,x-B,x-C,分别进行维护。

   如果x-A与y-B为同一组,那么就代表 动物x为A种类且动物y为B种类。

   所以,对上面两种信息,可以分别进行下面的操作:

   第一种,x和y为同一种类,那么我们就把x-A与y-A,x-B与y-B,x-C与y-C放入一组(这样就能保证,若x为A,那么y也为A,或者若x为B,y为B...)

   第二种,x吃y,那么只有3情况:1,x为A且y为B;2,x为B且y为C;3,x为C且y为A;所以就把x-A,y-B....放入同一组

   不过在进行前面操作时,要判断是否有冲突。

 

AC代码:

#include <cstdio>
using namespace std;
const int MAX_N = 50000;
int fa[3*MAX_N+1],n,x,y,t,k;
int find(int x)
{
	if(fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
}
void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if(x == y) return ;
	fa[x] = y;
}
bool same(int x, int y)
{
	return find(x) == find(y);
}

void init()
{
	for(int i = 1; i <= n*3; i++)
		fa[i] = i;
}
void solve()
{
	int ans = 0;
	while(k--)
	{
		scanf("%d %d %d", &t, &x, &y);
		//编号超界 
		if(x < 1 || x > n || y < 1 || y > n)
		{
			ans++;
			continue;
		}
		if(t == 1)
		{
			//判定x和y是不是同一种类 
			//如果x-A与y-B同一组说明,x为A种类且y为B种类,那么显然x和y不可能是同一种类,故该信息是假信息 
			//同理,如果x-A与y-C为同一组.... 
			if(same(x,y+n) || same(x,y+2*n) ) ans++;
			else 
			{
				unite(x,y);
				unite(x+n, y+n);
				unite(x+2*n, y+2*n);
			}
		}else
		{
			//判定x能否吃y
			//如果x等于y或者x为A,y为C,那么x不能吃y ,所以该信息为假信息 
			if(same(x,y) || same(x,y+2*n)) ans++;
			else
			{
				unite(x,y+n);
				unite(x+n,y+2*n);
				unite(x+2*n, y);
			}
		}
	}
	printf("%d\n", ans);
}
int main()
{
	scanf("%d %d", &n, &k);
	init();
	solve();
	return 0;
}