信息学奥赛一本通 1390：食物链【NOI2001】| 洛谷 P2024 [NOI2001] 食物链

【题目链接】

ybt 1390：食物链【NOI2001】
洛谷 P2024 [NOI2001] 食物链

【题目考点】

1. 种类并查集

2. 带权并查集

【解题思路】

解法1：种类并查集

已知有三类动物A、B、C。A吃B，B吃C，C吃A。
对于B类动物来说，A类动物是B类动物的天敌，C类动物是B类动物的猎物。
共有n个动物，对于动物$i$，假设$i+n$是$i$的一个天敌，假设$i+2n$是$i$的一个猎物。（$i+n$和$i+2n$是我们人为假设出来的并非1~n中任何动物的其他动物）
那么$i$，$i+n$，$i+2n$分别可能是A、B、C中的哪类动物？有以下几种情况。

A类动物	B类动物	C类动物
i+n	i	i+2n
i	i+2n	i+n
i+2n	i+n	i

设存在A、B、C三个集合，使用并查集表示这三个集合。那么调用find(i), find(i+n), find(i+2*n)就可以得到代表这三个集合的根结点的编号。

对于输入的动物编号x或y，如果x或y大于n，则该描述一定是假话

1. 如果输入1 x y，说x与y是同类
那么首先判断x与y是否是天敌与猎物的关系。

• 判断x是否是y的天敌，也就是判断$x$与$y+n$是否在同一集合中find(x) == find(y+n)。
• 判断x是否是y的猎物，也就是判断$x$与$y+2n$是否在同一集合中find(x) == find(y+2*n)

只要满足上述两条件之一，那么x与y不可能是同类，这句话是假话。
如果不满足上述条件，那么x与y是同类，二者所在集合合并merge(x, y)。
同时x的天敌与y的天敌是同类merge(x+n, y+n)，x的猎物与y的猎物是同类merge(x+2*n, y+2*n)
2. 如果输入2 x y，表示x吃y，也就是x是y的天敌，y是x的猎物
如果x是y的猎物，或x与y是同类，则这句话是假话

• 判断x是否y的猎物，也就是判断$x$与$y+2n$是否在同一集合中find(x) == find(y+2*n)。
• 判断x与y是否同类，也就是判断$x$与$y$是否在同一集合中find(x) == find(y)

只要满足上述两条件之一，那么x不可能是y的天敌，这句话是假话。
如果不满足上述条件，那么x与y的天敌是同类merge(x, y+n)，x的天敌与y的猎物是同类merge(x+n, y+2*n)，x的猎物与y是同类merge(x+2*n, y)。

统计并输出假话的数量，即为最终结果。

解法2：带权并查集（待完善）

【题解代码】

解法1：种类并查集

#include<bits/stdc++.h>
using namespace std;
#define N 50005
int fa[3*N], ans;//fa[i]：i的双亲，下标1~3*n。 
void initFa(int n)
{for(int i = 1; i <= n; ++i)fa[i] = i;
}
int find(int x)
{return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{fa[find(x)] = find(y);
}
int main()
{int n, k, op, x, y;cin >> n >> k;initFa(3*n);while(k--){cin >> op >> x >> y;if(x > n || y > n){ans++;continue;}if(op == 1)//x和y同类 {if(find(x) == find(y+n) || find(x) == find(y+2*n))ans++;else{merge(x, y);merge(x+n, y+n);merge(x+2*n, y+2*n);}}else//op == 2 x吃y {if(find(x) == find(y+2*n) || find(x) == find(y))ans++;else{merge(x, y+n);merge(x+n, y+2*n);merge(x+2*n, y);}}}cout << ans;return 0;
}