题目链接: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; }
Comments NOTHING