P2024 [NOI2001] 食物链（种类+ 拓展域并查集）

题目链接：P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

这道题我们不仅需要维护同类，还需要维护吃与被吃的关系，可以想到用拓展域并查集的思路。

这道题一共有3个五种A、B、C，一共N个动物所以我们要开3 * N的空间。

这里我们将这3N空间划分为3个部分，[1, N]表示物种A，[N + 1, 2 * N]表示物种B、[2 * N + 1, 3 * N]表示物种C。（未必一定是ABC，这里只是表示一个吃与被吃的关系。）

每新增一个关系，需要合并三对点（连接三条边）。

比如新增1 吃 2，那么就要将（1 -> N + 2）, （N + 1 -> 2 * N + 2）, （2 * N + 1 -> 2）这三条边分别连接起来。如图所示

最后查询1 和 2的关系只需要查询1和2、N+1和2*N+2、2*N+1和2的关系就可以了。

代码

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e4 + 10;
int pre[maxn * 3], N, K;
int root(int x){return pre[x] == x ? x : pre[x] = root(pre[x]);}

int relation(int x,int y)
{
	//1 -> x 与 y同类 
	//2 -> x 吃 y
	//3 -> y 吃 x
	//0 -> 关系未知 
	if(root(x) == root(y))return 1;
	else if(root(x) == root(N + y))return 2;
	else if(root(y) == root(N + x))return 3;
	return 0;
}

signed main()
{
	scanf("%lld %lld", &N, &K);
	for(int i = 1;i <= 3 * N; ++ i)pre[i] = i;
	int ans = 0;
	while(K --)
	{
		int op, x, y;scanf("%lld", &op);
		if(op == 1)
		{
			scanf("%lld %lld", &x, &y);
			//判断关系 
			if(x > N || y > N)ans ++;//先判断一下x y是否合法 
			else if(relation(x, y) == 0)//关系未知，真话、建立关系 
			{
				pre[root(x + N * 0)] = root(y + N * 0);
				pre[root(x + N * 1)] = root(y + N * 1);
				pre[root(x + N * 2)] = root(y + N * 2);
			}else if(relation(x, y) != 1)ans ++;//假话 
		}else if(op == 2)
		{
			scanf("%lld %lld", &x, &y);
			if(x > N || y > N || x == y)ans ++;//先判断一下x y是否合法 
			else if(relation(x, y) == 0)//关系未知，真话、建立关系 
			{
				pre[root(x + N * 0)] = root(y + N * 1);
				pre[root(x + N * 1)] = root(y + N * 2);
				pre[root(x + N * 2)] = root(y + N * 0);
			}else if(relation(x, y) != 2)ans ++;//假话
		}
	}
	printf("%lld\n", ans);
	return 0;
}