食物链(并查集) 维护权值写法,非常详细,适合新手服用

 题目描述: 

动物王国中有三类动物 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 句话有的是真的,有的是假的。

当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

  1. 当前的话与前面的某些真的话冲突,就是假话;
  2. 当前的话中 X 或 Y比 N 大,就是假话;
  3. 当前的话表示 X 吃 X,就是假话。

你的任务是根据给定的 N 和 K 句话,输出假话的总数。

输入格式

第一行是两个整数 N和 K,以一个空格分隔。

以下 K 行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中 D 表示说法的种类。

若 D=1,则表示 X 和 Y 是同类。

若 D=2,则表示 X 吃 Y。

输出格式

只有一个整数,表示假话的数目。

数据范围

1≤N≤50000,
0≤K≤1000000

输入样例:
100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5
输出样例:
3

思路: 

首先我们要知道并查集中每一个集合以树的形式进行存储
此题需要我们维护的信息是d[](节点边的权值)。

 从此图中我们还可以发现,此图为一个有向图且成一个环形状,可以推出3个动物一循环

所以我们只需要知道两个动物的关系,放到集合中,集合中所有动物的关系,我们是一定可以退出来的。


我们思考一个位置,如果推出来的呢? 

例如:x与y是同类,y被z吃,我们是不是可以推出来x也被z吃呢

再比如:x吃y, y吃z,通过上面我们画的有向图,是不是也能推出来z吃x呢。因为是一个环形有向图吗,所以一定可以推出来的这里就不画图了,类比上面的图。


那么我们如何确定一个集合里面的动物之间关系呢? 

我们只需要找出此点根节点之间的关系即可。

例如:如下图


下面我们来看一下代码。 


 AC代码:

//首先我们要知道并查集中每一个集合以树的形式进行存储
//此题需要我们维护的信息是d[](节点边的权值)。
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e4+10;
int n,m;
//p[]->存出父亲节点,d[]->i到用来存储到根节点的距离
//刚开始自己一个类所以d[]都是0
int p[N],d[N];

//路径压缩,顺势求出每个点到根节点的距离
int find(int x)
{
    //如果不是根节点就执行
    if(p[x] != x)
    {
        //用来存储一下根节点,为了不影响后面求x到根节点的值
        int t = find(p[x]);
        //累加求出x(该点)到根节点的值
        d[x] += d[p[x]];
        p[x] = t;//指向根节点,路径压缩成功
    }
    return p[x];//返回父亲节点
}

int main()
{
    int res = 0;//计算假的个数
    scanf("%d%d", &n, &m);
    //刚开始自己为单独一个集合
    for(int i=1;i<=n;i++) p[i] = i;
    while (m -- )
    {
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        //当前的话中 X或 Y比 N大,就是假话 
        if(x > n || y > n)
            res ++;
        else
        {   
            //分别求一下两个动物的根节点,为了后面确认关系
            int px = find(x),py = find(y);
            //同类
            if(t==1)
            {
                //如果在一个根节点下,要保证d[x] % 3 == d[y] % 3 ---> (d[x] - d[y])%3==0
                if(px == py && (d[x] - d[y])%3) res++;
                //如果不在一个根节点下
                else if(px!=py)
                {
                    //不妨让x编号根节点合并到y编号下根节点下。也就是py是px的父亲节点
                    p[px] = py;
                    //d[x] + ? - d[y] = 0 -- > ? = d[y] - d[x];
                    d[px] = d[y] - d[x];
                }
            }
            else//被吃的关系
            {
                //如果在一个根节点下,x吃y,第0代被第1代吃,第一代被第二代吃,第三代吃第二代
                //可以知道x是比y到根节点距离多1的,所以(d[x] - d[y] - 1)%3 = 0;
                if(px == py && (d[x] - d[y] - 1) % 3) res++;
                else if(py!=px)
                {
                    p[px] = py;
                    //d[x] + ? - 1 - d[y] = 0 ---> ? = d[y] + 1 - d[x];
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
       
    }
    printf("%d",res);
    return 0;
}

上述代码大家可能会疑问,d都初始化为0了,那无论d[x]加多少次d[p[x]],结果都是0啊 ? 

d[px] = d[y] + 1 - d[x];

我们可以看到此代码,在我们插入两个动物关系的时候,这里已经有+1的操作了,所以我们不用担心这个问题。


 第二个有问题的地方可能是find函数那里

int find( int x ) {
if( p[x] != x ) {
// int t = find( p[x] );
d[x] += d[p[x]];
p[x] = find( p[x] );
}
return p[x];
}

为什么不可以上面那么写,一定要像下面那么写呢?

int find( int x ) {
if( p[x] != x ) {
int t = find( p[x] );
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}

这里推荐大家手动模拟一遍,然后看一下两者的区别,第一种只能去求出到父亲节点的距离,并不能够达到累加求到根节点的距离,相比之下,第二种可以。 


对于这段代码图解:


对于这段代码图解:

 注意X到根的距离比Y多1,因为是X吃Y,可以根据上面图理解一下


对于find函数里的递归如下:

此图来源于acwing题解中一位大佬的图解,原图在:AcWing 240. 食物链---数组d的真正含义以及find()函数调用过程 - AcWing


欢迎不会的小伙伴留言~ 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/510891.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

YOLOv8全网独家改进: 小目标 | CAMixing:卷积-注意融合模块和多尺度提取能力 | 2024年4月最新成果

💡💡💡本文独家改进:CAMixingBlock更好的提取全局上下文信息和局部特征,包括两个部分:卷积-注意融合模块和多尺度前馈网络; 💡💡💡红外小目标实现涨点,只有几个像素的小目标识别率提升明显 💡💡💡如何跟YOLOv8结合:1)放在backbone后增强对全局和局部特…

[lesson02]C到C++的升级

C到C的升级 C与C的关系 C继承了所有的C特性C在C的基础上提供了更多的语法和特性C的设计目标是运行效率与开发效率的统一 C到C的升级 C更强调语言的实用性 所有的变量都可以在需要使用时再定义 int c 0; for (int i 1; i < 3; i) {for(int j 1; j < 3; j){c i * …

隐私计算实训营第六讲-隐语PIR介绍及开发实践

隐私计算实训营第六讲-隐语PIR介绍及开发实践 文章目录 隐私计算实训营第六讲-隐语PIR介绍及开发实践1.隐语实现PIR总体介绍1.1按服务器数量分类1.2按查询类型分类 2. Index PIR - SealPIR3. Keyword PIR - Labeled PSI4.隐语PIR功能分层5.隐语PIR后续计划PIR协议开发PIR调用框…

坦白局:PMP真的是智商税吗?

近些年报考PMP认证的学员越来越多&#xff0c;PMP全球持证人数已经突破百万了&#xff0c;据PMI统计&#xff0c;IT行业近50%人士都持有PMP证书&#xff0c;因此也有很多学员在思考&#xff0c;PMP持证人员这么多&#xff0c;PMP是不是都已经烂大街了&#xff1f;证书还有含金量…

【浅尝C++】STL第三弹=>list常用接口使用示例/list底层结构探索/list模拟实现代码详解

&#x1f3e0;专栏介绍&#xff1a;浅尝C专栏是用于记录C语法基础、STL及内存剖析等。 &#x1f3af;每日格言&#xff1a;每日努力一点点&#xff0c;技术变化看得见。 文章目录 list介绍list常用接口使用示例构造类函数迭代器属性与元素获取增删改操作 list底层结构探索list模…

2024年03月CCF-GESP编程能力等级认证Scratch图形化编程一级真题解析

本文收录于专栏《Scratch等级认证CCF-GESP真题解析》,专栏总目录・点这里 一、单选题(每题 3 分,共 30 分) 第1题 小杨的父母最近刚刚给他买了一块华为手表,他说手表上跑的是鸿蒙,这个 鸿蒙是?( )。 A、小程序 B、计时器 C、操作系统 D、神话人物 答案:C 第2题 …

golang语言系列:Web框架+路由 之 Gin

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是golang语言学习系列&#xff0c;本篇对Gin框架的基本使用方法进行学习 1.Gin框架是什么 Gin 是一个 Go (Golang) 编写的轻量级 http web 框架&#xff0c;运行速度非常快&#xff0c;如果你是性能和高效的追求者…

HBase基础必备知识-Day1

HBase 简介 概述 HBase是Yahoo!公司开发的后来贡献给了Apache的一套开源的、分布式的、可扩展的、基于Hadoop的非关系型数据库(Non-Relational Database)&#xff0c;因此HBase并不支持SQL(几乎所有的非关系型数据库都不支持SQL)&#xff0c;而是提供了一套单独的命令和API操…

Redis高可用及持久化

文章目录 一、Redis高可用1、Redis高可用概述2、Redis高可用策略 二、Redis持久化1、Redis持久化的功能2、Redis持久化的两种方式2.1 RDB持久化2.2 AOF持久化&#xff08;append only file&#xff09; 3、RDB持久化3.1 触发条件3.1.1 手动触发3.1.2 自动触发3.1.2.1 配置方式3…

[Linux] 排查问题指令top/ps/netstat

在Linux下查看某个端口运行的指令 1. 首先通过netstat来查看端口对应的进程号 比如抓取端口53这个DNS服务的进程 netstat -tulnp | grep 53 可以看到53这个端口号对应的pid是720 2. 通过ps指令来对进程号执行的命令查询 ps aux | grep 720 可以看到pid为720这个进程对应的执…

聚道云助IT公司破解数据同步难,高效转型新利器!

客户介绍&#xff1a; 该公司是一家在信息技术行业具有丰富经验和良好声誉的公司。作为专业的软件服务提供商&#xff0c;他们致力于为客户提供全方位的解决方案和支持服务。公司秉持合规经营的原则&#xff0c;严格遵守相关法律法规&#xff0c;确保客户的数据安全和合法权益…

HTML基础:脚本 script 标签

你好&#xff0c;我是云桃桃。 1枚程序媛&#xff0c;大专生&#xff0c;2年时间从1800到月入过万&#xff0c;工作5年买房。 分享成长心得。 255篇原创内容-公众号 后台回复“前端工具”可获取开发工具&#xff0c;持续更新中 后台回复“前端基础题”可得到前端基础100题汇…

图卷积神经网络GCN

图卷积神经网络GCN 我们的GCN就是用来解决如何确定a、b、c的

Java毕业设计-基于springboot开发的致远汽车租赁系统平台-毕业论文+答辩PPT(附源代码+演示视频)

文章目录 前言一、毕设成果演示&#xff08;源代码在文末&#xff09;二、毕设摘要展示1、开发说明2、需求分析3、系统功能结构 三、系统实现展示1、系统功能模块2、管理员功能模块3、业务员功能模块3、用户功能模块 四、毕设内容和源代码获取总结 Java毕业设计-基于springboot…

Sora 基础作品之 DiT:Scalable Diffusion Models with Transformer

Paper name Scalable Diffusion Models with Transformers (DiT) Paper Reading Note Paper URL: https://arxiv.org/abs/2212.09748 Project URL: https://www.wpeebles.com/DiT.html Code URL: https://github.com/facebookresearch/DiT TL;DR 2022 年 UC Berkeley 出…

LeetCode 59 螺旋矩阵(模拟)

给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[[1,2,3],[8,9,4],[7,6,5]]示例 2&#xff1a; 输入&#xff1a;n 1 输出&…

模型训练----parser.add_argument添加配置参数

现在需要配置参数来达到修改训练的方式&#xff0c;我现在需要新建一个参数来开关wandb的使用。 首先就是在def parse_option():函数里添加上你要使用的变量名 parser.add_argument("--open_wandb",type bool,defaultFalse,helpopen wandb) 到config文件里增加你的…

2024-04-02 作业

作业要求&#xff1a; 整理思维导图使用模板类&#xff0c;实现顺序栈写一个char类型的字符数组&#xff0c;对该数组访问越界时抛出异常&#xff0c;并做处理。 作业1&#xff1a; 作业2&#xff1a; 运行代码: #include <iostream>using namespace std; #define LEN …

OpenGL_Learn16(模板测试)

模板缓冲首先会被清除为0&#xff0c;之后在模板缓冲中使用1填充了一个空心矩形。场景中的片段将会只在片段的模板值为1的时候会被渲染&#xff08;其它的都被丢弃了&#xff09;。 模板缓冲操作允许我们在渲染片段时将模板缓冲设定为一个特定的值。通过在渲染时修改模板缓冲的…

LeetCode_394(字符串解码)

双栈法 public String decodeString(String s) {String res "";Stack<Integer> countStack new Stack<>();Stack<String> resStack new Stack<>();int idx 0;while (idx < s.length()){char cur s.charAt(idx);//处理数字if(Charact…