本文共 4788 字，大约阅读时间需要 15 分钟。

题目描述

动物王国中有三类动物 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 ，表示有 N 个动物，K 句话。第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

输入输出样例

输入 #1

100 71 101 12 1 22 2 32 3 31 1 32 3 11 5 5

输出 #1

3

说明/提示：$1\le N\le 5\times 10^4$ , $1\le K\le 10^5$ 。

题意：找出假话有多少句。

---

思路：三个及以上的集合，只要集合间的关系都是循环对称的，就能够用种类并查集来维护。本题中，A 吃 B ，B 吃 C ，C 吃 A 。恰好适应这个规则。

设我们有 $n$ 个动物，开 $3n$ 大小的种类并查集，其中 $1\sim n$ 的部分为 $A$ 群系，$n+1\sim 2n$ 的部分为 $B$ 群系，$2n+1\sim 3n$ 的部分为 $C$ 群系。我们可以认为：

• $A$ 表示中立者，$B$ 表示生产者，$C$ 表示消费者。此时关系：$A$ 吃 $B$ ，$A$ 被 $C$ 吃。
• 或者 $B$ 是中立者，这样 $C$ 就成为了生产者，$A$ 就表示消费者。此时关系：$B$ 吃 $C$ ，$B$ 被 $A$ 吃。
• 或者 $C$ 是中立者，这样 $A$ 就成为了生产者，$B$ 就表示消费者。此时关系：$C$ 吃 $A$ ，$C$ 被 $B$ 吃。

联想一下 $2$ 倍并查集的做法，就有：

• 当 $A$ 中的 $x$ 与 $B$ 中的 $y$ 合并，有关系 $x$ 吃 $y$ ；
• 当 $B$ 中的 $x$ 与 $C$ 中的 $y$ 合并，有关系 $x$ 吃 $y$ ；
• 当 $C$ 中的 $x$ 和 $C$ 中的 $y$ 合并，有关系 $x$ 和 $y$ 同类；
• ……

当然，我们不知道某个动物属于 $A,B,C$ 中的哪一种，所以 $3$ 个种类都要试一试。于是每当出现一句真话时，需要合并 $3$ 组元素。

下面举出详细例子。有以下的输入数据：

4 51 1 32 2 42 3 21 1 42 2 1

涉及 $4$ 个动物，构建下面的初始并查集：

先看第 $1$ 句话：动物 $1$ 和 $3$ 是同类的。我们可以在 $3$ 个群系中分别给 $1$ 和 $3$ 的集合合并，以表示动物 $1$ 和 $3$ 是一定友好的。

再看第 $2$ 句话：动物 $2$ 吃 $4$ 。显然这不矛盾。但我们不知道 $2$ 和 $4$ 对应 $A,B,C$ 中的哪个，所以只能根据 $A$ 吃 $B$ ，合并 $A$ 群系中的 $2$ 和 $B$ 群系中的 $4$ ；再根据 $B$ 吃 $C$ 和 $C$ 吃 $A$ ，作出对应的处理。结果如下所示：

看第 $3$ 句话：动物 $3$ 吃 $2$ 。这是句真话，具体判断方法看下面两句话。暂且先作出以下处理：

---

第 $4$ 句话中 $1$ 和 $4$ 是同类。此时解释如何判断话的真假。对于同类动物，转换一下，如果知道 $1$ 不吃 $4$ 且 $4$ 不吃 $1$ ，不就是同类了吗？所以如何判断动物 $x$ 吃动物 $y$ ？

我们知道如果要表示动物 $x$ 吃动物 $y$ ，只要根据 $A$ 吃 $B$ ，把 $A$ 群系中的 $x$ 和 $B$ 群系中的 $y$ 合并即可。另外 $2$ 次合并暂不讨论。反过来讨论，如果 $A$ 群系中的 $x$ 已经和 $B$ 群系中的 $y$ 在同一集合中了，不就表示了动物 $x$ 吃动物 $y$ 吗？

于是看到上面那张图，$B$ 群系中的 $1$ 按照并查集的递归操作，找出自己的终极上级是 $A$ 群系中的 $4$ 。分析其含义，属于 $B$ 群系的 $1$ 已经与 $A$ 群系的 $4$ 处于同一集合，应有 $4$ 吃 $1$ ，而非同类。第 $4$ 句话是假的。

第 $5$ 句话 $2$ 吃 $1$ 。我们需要判断 $2$ 和 $1$ 不是同类并且 $2$ 不被 $1$ 吃即可。判断是否同类，我们同样可以反过来讨论：判断在同个群系中的 $2$ 和 $1$ 的集合是否已经合并。得出 $2$ 和 $1$ 不是同类后，我们再看 $1$ 是否吃 $2$ 。看图，$A$ 群系中的 $1$ 和 $B$ 群系中的 $2$ 在同一集合中，得出 $1$ 吃 $2$ 。第 $5$ 句话也是假话。

因此有两句假话。输出 $2$ ，问题完美解决。

---

上述过程，写成具体代码如下：

#include 
   
    using namespace std;const int maxn = (5e4 + 10) * 3;int father[maxn], height[maxn];void init(int n) {
   	for (int i = 1; i <= n; ++i) father[i] = i, height[i] = 1;	}int find(int x) {
   	return father[x] == x ? x : father[x] = find(father[x]);}void merge(int a, int b) {
   	int x = find(a), y = find(b);	if (x == y) return;	if (height[x] >= height[y]) father[y] = x;	else father[x] = y;	if (height[x] == height[y]) ++height[x];}bool query(int a, int b) {
    return find(a) == find(b); }int main() {
    	int n, k, op, a, b;	scanf("%d%d", &n, &k);	init(3 * n);	int falseNum = 0;	for (int i = 0; i < k; ++i) {
   		scanf("%d%d%d", &op, &a, &b);		if (a > n || b > n) 			++falseNum;  		else if (op == 1) {
    //说话表示a和b是同类 			if (query(a, b + n) || query(b, a + n)) //已知A的a吃B的b或者A的b吃B的a 				++falseNum; 			else {
       		//是真话 				merge(a, b); 					//A中a、b是同类 				merge(a + n, b + n);			//B中a、b是同类 				merge(a + 2 * n, b + 2 * n);    //C中a、b是同类 			}		} 		else if (op == 2) {
    //说话表示a吃b 			if (query(a, b) || query(b, a + n)) //已知A的a、b是同一族或者A的b吃a 				++falseNum;			else {
   			//是真话				merge(a, b + n);				//A的a吃B的b 			 	merge(a + n, b + 2 * n);		//B的a吃C的b 				merge(a + 2 * n, b); 			//C的a吃A的b 			}		}	}	printf("%d\n", falseNum);    return 0;}
   

---

或者更简单的视角是，i 的猎物是与 i + n 在同一集合的其他动物，i 的天敌是与 i + 2n 在同一集合的其他动物。于是代码如下：

//......//并查集代码一致int main() {
    	int n, k, op, a, b;	scanf("%d%d", &n, &k);	init(3 * n);	//i的猎物是i+n(同一集合的动物),i的天敌是i+2*n(同一集合的动物) 	int falseNum = 0;	for (int i = 0; i < k; ++i) {
   		scanf("%d%d%d", &op, &a, &b);		if (a > n || b > n) 			++falseNum;  		else if (op == 1) {
    //说话表示a和b是同类 			if (query(a + n, b) || query(a + 2 * n, b)) //已知a吃b或者a被b吃 				++falseNum; 			else {
       		//是真话 				merge(a, b); 					//a的同类是b的同类 				merge(a + n, b + n);			//a的猎物和b的猎物同一族 				merge(a + 2 * n, b + 2 * n);    //a的天敌和b的天敌同一族 			}		} 		else if (op == 2) {
    //说话表示a吃b 			if (query(a, b) || query(a + 2 * n, b)) //已知a和b是同一族或者a被b吃				++falseNum;			else {
   			//是真话				merge(a + n, b);				//a的猎物是b的同类 			 	merge(a, b + 2 * n);			//a的同类是b的天敌 				merge(a + 2 * n, b + n); 		//a的天敌(c)是b的猎物(c) 			}		}	}	printf("%d\n", falseNum);    return 0;}

转载地址：https://memcpy0.blog.csdn.net/article/details/108288162 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！