算法刷题笔记 食物链(详细注释的C++实现)
题目描述
- 动物王国中有三类动物
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
基本思路
- 本题的难点在于使用并查集的过程中维护额外的距离信息。
- 另外,以后使用
if
和else if
语句的时候,一定要注意是否忽略了潜在的第三种情况,否则容易导致代码出错。 - 具体的解题思路请参见代码注释。
实现代码
#include <cstdio>
// 分别用整型变量n和整型变量k表示动物的总数和论述的总数
int n, k;
// 用于表示指定编号的动物所属的集合编号的数组(初始情况下,每只动物所属的集合的编号与该动物本身的编号相同)
const int N = 5e4 + 10;
int animals[N];
// 用于表示每一个表示动物的结点到所属集合的根节点的距离的数组(初始情况下,每个结点都是该集合的根节点,因此距离为0)
int distances[N];
// 用于初始化每一个集合的编号的函数
void init_sets(void)
{
// 初始情况下,每只动物对应的集合编号和动物本身的编号相同,到集合的根节点的距离应该为0
for(int i = 1; i <= n; ++ i)
{
animals[i] = i;
distances[i] = 0;
}
}
// 更新指定元素所在的集合的编号并进行路径压缩的函数
int find_set(int x)
{
// 如果当前元素的编号和集合的编号不同,说明该元素不是根节点,需要逐一向上找到该元素的根节点
// 在寻找根节点的过程中,将路上经过的所有节点都直接指向根节点,进行路径压缩优化
if(x != animals[x])
{
int parent = animals[x]; // 记录当前结点的父节点
animals[x] = find_set(animals[x]); // 将当前节点所属集合的根节点设置为该节点的父结点,进行路径压缩
distances[x] += distances[parent]; // 更新当前节点距离根节点的距离
}
// 将当前元素所属的集合的编号(也就是更新后的根节点的编号)返回
return animals[x];
}
// 判断一条论述是否是真话的函数
bool judge_statement(int d, int x, int y)
{
// 早退情况:x或y超出了合理范围,则一定是假话
if(x > n || y > n) return false;
// x和y都在合理范围内的情况
else
{
// 情况1:该论述判定某两只动物属于同类
if(d == 1)
{
// 如果x和y两只动物在先前的论述中都提到过,且两者不属于同类,才能证明当前论述错误
if((find_set(x) == find_set(y)) && ((distances[x] - distances[y]) % 3 != 0)) return false;
// 如果不满足上述条件,且两只动物不在同一个集合中,则将两只动物所在的集合合并
else if(animals[x] != animals[y])
{
// 首先找到动物x所属集合的根节点的编号
int x_root = animals[x];
// 将动物y的根节点所属的集合修改为动物x所属的集合
animals[x_root] = animals[y];
// 更新距离
distances[x_root] = distances[y] - distances[x];
// 返回真值
return true;
}
// 如果x和y两只动物在同一个集合中,且属于同类,则当前论述正确
else return true;
}
// 情况2:该论述判定x吃y
else if(d == 2)
{
// 只有在x和y两只动物在先前的论述中都提到过,但是两者不存在论述中的捕食关系,才能证明当前论述错误
if((find_set(x) == find_set(y)) && ((distances[y] - distances[x] + 1) % 3 != 0)) return false;
// 如果不满足上述的条件,且两只动物不在同一个集合中,则将两个动物所在的集合合并
else if(animals[x] != animals[y])
{
// 首先找到动物x所属集合的根节点的编号
int x_root = find_set(x);
// 将元素x所属的集合与元素y所属的集合合并
animals[x_root] = animals[y];
// 更新距离
distances[x_root] = distances[y] - distances[x] + 1;
// 返回真值
return true;
}
// 如果x和y两只动物都在同一个集合中,且存在论述中的捕食关系,则当前论述正确
else return true;
}
}
}
int main(void)
{
// 变量输入部分
scanf("%d%d", &n, &k);
// 对并查集集合列表进行初始化
init_sets();
// 通过循环,查找假话的数量
int false_statement = 0;
for(int i = 0; i < k; ++ i)
{
int d, x, y;
scanf("%d%d%d", &d, &x, &y);
// 判断当前说法的类型
if(judge_statement(d, x, y) == false) ++ false_statement;
}
printf("%d", false_statement);
return 0;
}
原文地址:https://blog.csdn.net/hanmo22357/article/details/140432822
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!