食物链
动物王国中有三类动物 A,B,C 这三类动物的食物链构成了有趣的环形。
A 吃 B,B 吃 C,C 吃 A。
现有 N 个动物,以 1∼N 编号。
每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述:
第一种说法是 1 X Y ,表示 X 和 Y 是同类。
第二种说法是 2 X Y ,表示 X 吃 Y。
此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。
当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
- 当前的话与前面的某些真的话冲突,就是假话;
- 当前的话中 X 或 Y 比 N 大,就是假话;
- 当前的话表示 X 吃 X,就是假话。
你的任务是根据给定的 N 和 K 句话,输出假话的总数。
输入格式
第一行是两个整数 N 和 K,以一个空格分隔。
以下 K 行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中 D 表示说法的种类。
若 D=1,则表示 X 和 Y 是同类。
若 D=2,则表示 X 吃 Y。
输出格式
只有一个整数,表示假话的数目。
数据范围
1 ≤ N ≤ 50000,
0 ≤ K ≤ 100000
输入样例:
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
输出样例:
3
解题思路
这道题主要的思路是并查集。不过并不是朴素并查集,而是并查集的拓展,在这题里可以用到种类并查集和带权重并查集这两种。
只学过朴素并查集的我表示,当时这道题写了1个多小时,思路很乱代码很复杂,结果也是WA。后来去看题解发现用到的方法完全没有学过,当时看了一天也没有理解,真的太难受了。现在开始有所理解了。
种类并查集
种类并查的本质是维护一种循环对称的关系,所以如果是两个及以上的集合,只要每个集合都是等价的,且集合间的每个关系都是等价的,就能够用种类并查集进行维护。比如下图:
如果关系指的是“敌人”,那么集合A中的元素与集合B中的元素构成敌人关系,集合B中的元素与集合A中的元素构成敌人关系。这两种关系是循环、等价的,对应那两个箭头。
比如这道题目我们有这三个集合:
然后并不是直接开三个并查集来代表A,B,C,而是开一个容量为3倍的并查集。其中有 i∈[1, n] ,那么有如下规定: i + n 被 i 捕食,也就是说 i + n 是 i 的猎物, i 被 i + 2*n 捕食,也就是说 i + 2*n 是 i 的天敌。实际上如果给定两个动物,我们并不知道他们到底是A,B,C中的哪一类,合并的时候都是根据捕食这一个关系来合并的。
有x和y这两种动物,如果判定x和y是同一个物种,那么同时也意味着x的猎物与y的猎物是同一物种,x的天敌和y的天敌也是同一物种。然后我们进行归并操作:
merge(x, y); merge(x + n, y + n); merge(x + 2*n, y + 2*n);
如果判定为x捕食y,那么意味着y是x的猎物,又因为我们规定x + n是x的猎物,所以有y与x + n一类,都是x的猎物。剩下的关系我们可以画个图来理解,以此类推:
双箭头表示这两个动物都是属于同一个集合的,所以有如下的归并操作:
merge(y, x + n); merge(x + 2*n, y + n); merge(x, y + 2*n);
AC代码:
1 #include <cstdio> 2 using namespace std; 3 4 const int N = 5e4 + 10; 5 6 int p[3 * N]; 7 8 int find(int x) { 9 return p[x] == x ? x : p[x] = find(p[x]); 10 } 11 12 int main() { 13 int n, m; 14 scanf("%d %d", &n, &m); 15 for (int i = 1; i <= 3 * n; i++) { 16 p[i] = i; 17 } 18 19 int ret = 0; 20 while (m--) { 21 int op, x, y; 22 scanf("%d %d %d", &op, &x, &y); 23 24 if (x > n || y > n) { 25 ret++; 26 continue; 27 } 28 29 if (op == 1) { // 说明x和y是同物种 30 // 如果x捕食y,或者y捕食x,就说明x和y不是同物种,是假话 31 // 代码解释:如果发现y与x + n是同一个集合,说明y是x的猎物;如果发现x与y + n是同一个集合,说明x是y的猎物 32 if (find(y) == find(x + n) || find(x) == find(y + n)) { 33 ret++; 34 } 35 else { 36 p[find(x)] = find(y); // x和y是同一物种 37 p[find(x + n)] = find(y + n); // x的猎物与y的猎物是同一物种 38 p[find(x + 2 * n)] = find(y + 2 * n); // x的天敌与y的天敌是同一物种 39 } 40 } 41 else { // 说明x捕食y 42 if (x == y) { 43 ret++; 44 continue; 45 } 46 // 如果x和y是同一物种,或者y捕食x,就说明x捕食y是假话 47 // 代码解释:如果发现y与x是同一个集合,说明x与y是同一物种;如果发现x与y + n是同一个集合,说明x是y的猎物,也就是y捕食x 48 if (find(x) == find(y) || find(x) == find(y + n)) { 49 ret++; 50 } 51 else { 52 // 对应的物种都合并至一类 53 p[find(y)] = find(x + n); 54 p[find(x + 2 * n)] = find(y + n); 55 p[find(x)] = find(y + 2 * n); 56 } 57 } 58 } 59 60 printf("%d", ret); 61 62 return 0; 63 }
带权重并查集
这个也有点难理解。
带权重并查集就不需要扩大3倍了,并查集的大小就是n。
举个例子来理解,假如有1,2,3,4,5这些动物,然后有1吃2,2吃3,3吃4,4吃5,我们来画一个图:
这里区分每个动物属于哪一类,用到了一个d[]数组。d[i]的含义是i到它的前一个节点(即p[i])的距离。由于在调用find函数时会路径压缩,所以每次查找一个节点后,该节点(包括路径上的节点)会直接指向根节点,所以d[i]自然就会表示为i到根节点的距离。
我们根据两个动物到根节点的距离来判他们是什么关系。
- 如果有(d[x] - d[y]) % 3 == 0 ,说明x与y是同一物种。
- 如果有(d[x] - d[y] - 1) % 3 == 0 ,说明x捕食y(这种写法考虑到d[x] = 0,d[y] = 2的情况)。
AC代码:
1 #include <cstdio> 2 using namespace std; 3 4 const int N = 5e4 + 10; 5 6 int p[N], d[N]; 7 8 int find(int x) { 9 if (p[x] != x) { 10 // 不可以直接写p[x] = find(p[x]); d[x] += d[p[x]]; 11 // 这样p[x]已经赋值为根节点了,d[x] += d[p[x]];加的是根节点到根节点的距离,并不是我们认为的p[x]到根节点的距离 12 // 因此先记录根节点,加上p[x]到根节点的值后,才将p[x]赋值为根节点 13 int px = find(p[x]); 14 d[x] += d[p[x]]; // 由于路径压缩,所以d[x]应改为x到根节点的距离,也就是原来的d[x]加上p[x]到根节点的距离(递归回来的时候p[x]已经指向根节点了,d[p[x]]自然也就更新成p[x]到根节点的距离) 15 p[x] = px; 16 } 17 18 return p[x]; 19 } 20 21 int main() { 22 int n, m; 23 scanf("%d %d", &n, &m); 24 for (int i = 1; i <= n; i++) { 25 p[i] = i; 26 } 27 28 int ret = 0; 29 while (m--) { 30 int op, x, y; 31 scanf("%d %d %d", &op, &x, &y); 32 33 if (x > n || y > n) { 34 ret++; 35 continue; 36 } 37 38 int px = find(x), py = find(y); 39 if (op == 1) { 40 if (px == py && (d[x] - d[y]) % 3) { 41 ret++; 42 } 43 else if (px != py) { 44 p[px] = py; 45 d[px] = d[y] - d[x]; // px到根节点py的距离不清楚,所以要求,(d[x] + ? - d[y]) % 3 = 0 -> ? = d[y] - d[x] 46 } 47 } 48 else { 49 if (x == y) { 50 ret++; 51 continue; 52 } 53 54 if (px == py && (d[x] - d[y] - 1) % 3) { 55 ret++; 56 } 57 else if (px != py) { 58 p[px] = py; 59 d[px] = d[y] - d[x] + 1; // px到根节点py的距离不清楚,所以要求,(d[x] + ? - d[y] - 1) % 3 = 0 -> ? = d[y] - d[x] + 1 60 } 61 } 62 } 63 64 printf("%d", ret); 65 66 return 0; 67 }
不知道有没有人会看到我的这篇blog,如果看不懂可以看看这到题目的视频讲解:https://www.acwing.com/video/251/
参考资料
算法学习笔记(7):种类并查集:https://zhuanlan.zhihu.com/p/97813717
AcWing 240. 食物链 (算法基础课):https://www.acwing.com/video/251/