[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
输入样例:
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例:
3
代码:
#include<iostream>
using namespace std;const int N = 50010;
int father[N],d[N];int findroot(int x){if(father[x] != x){int temp = findroot(father[x]);d[x] += d[father[x]];father[x] = temp;}return father[x];
}int main(){int n,k;cin>>n>>k;for(int i = 0;i<n;i++){father[i] = i;d[i] = 0;}int fake = 0;while(k--){int op;cin>>op;int x,y;cin>>x>>y;if(x > n || y > n){fake++;}else{int px = findroot(x);int py = findroot(y);if(op == 1){if((px == py) && ((d[x]-d[y])%3!= 0)){fake++;}else if(px != py){father[px] = py;d[px] = d[y] - d[x];}}else if(op == 2){if((px == py) && ((d[x]-d[y]-1)%3!= 0)){fake++;}else if(px != py){father[px] = py;d[px] = d[y] - d[x] + 1;}}}}cout<<fake<<endl;return 0;
}
相关文章:
[C++][算法基础]食物链(并查集)
动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。 A 吃 B,B 吃 C,C 吃 A。 现有 N 个动物,以 1∼N 编号。 每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这 N…...
深入理解Transformer的位置编码机制
Transformer架构由于其独特的设计,不像传统的循环神经网络(RNN)或卷积神经网络(CNN),它无法自然地处理序列数据中的顺序信息。为了使模型能够理解序列中各元素的位置关系,Transformer引入了一种…...

10分钟上手:MySQL8的Json格式字段使用总结干货
一、关于效率和适用范围 尽管官方承诺Json格式字段采用了空间换时间的策略,比Text类型来存储Json有大幅度的效率提升。但是Json格式的处理过程仍然效率不及传统关系表,所以什么时候用Json格式字段尤为重要。 只有我们确定系统已经能精确定位到某一行&am…...

OpenCV 4.9基本绘图
返回:OpenCV系列文章目录(持续更新中......) 上一篇:OpenCV使用通用内部函数对代码进行矢量化 下一篇:使用OpenCV4.9的随机生成器和文本 目标 在本教程中,您将学习如何: 使用 OpenCV 函数 line() 画一…...

显示器and拓展坞PD底层协商
简介: PD显示器或者PD拓展坞方案中,连接显示设备的Type-C端口主要运行在DRP模式,在此模式下可以兼容Source(显卡)、Sink(信号器)、DRP(手机、电脑)模式的显示设备。 Sou…...

如何利用Flutter将应用成功上架至iOS平台:详细指南
引言 🚀 Flutter作为一种跨平台的移动应用程序开发框架,为开发者提供了便利,使他们能够通过单一的代码库构建出高性能、高保真度的应用程序,同时支持Android和iOS两个平台。然而,完成Flutter应用程序的开发只是第一步…...

【运输层】网络数据报协议 UDP
目录 1、UDP 的特点 2、UDP 的首部格式 UDP 只在 IP 协议之上增加了很少的一些功能,比如复用、分用以及差错检测等。 1、UDP 的特点 UDP是无连接的,即发送数据之前不需要建立连接,因此减少了开销和发送数据之前的时延。 UDP使用尽最大努力…...
数据结构(初阶):顺序表实战通讯录
前言 数据结构(初阶)第一节:数据结构概论-CSDN博客 数据结构(初阶)第二节:顺序表-CSDN博客 本文将以C语言和顺序表实现通讯录基础管理,实现功能包括增、删、改、查等,在实现相关功能…...

Outlook会议邀请邮件在答复后就不见了
时常会有同事找到我说,Outlook答复会议邀请邮件后收件箱就找不到会议邀请的邮件了。 这其实是Outlook的的一个机制,会把应答后的会议邀请邮件从收件箱自动删除,到已删除的邮件那里就能找到。如果不想要自动删除,改一个设置即可。…...

【C++】list模拟实现
个人主页 : zxctscl 如有转载请先通知 文章目录 1. 前言2. list源码3. 初始化3.1 构造3.2 拷贝构造3.3 赋值3.4 析构 4. 迭代器4.1 后置加加和前置加加4.2 后置减减和前置减减4.3 解引用4.4 !和4.5 begin 和 end4.6 const迭代器4.7 迭代器优化 5. Modifi…...

ETL工具-nifi干货系列 第八讲 处理器PutDatabaseRecord 写数据库(详细)
1、本节通过一个小例子来讲解下处理器PutDatabaseRecord,该处理器的作用是将数据写入数据库。 如下流程通过处理器GenerateFlowFile 生成数据,然后通过处理器JoltTransformJSON转换结构,最后通过处理器PutDatabaseRecord将数据写入数据库。如…...

【MySQL】如何判断一个数据库是否出问题
在实际的应用中,其实大多数是主从结构。而采用主备,一般都需要一定的费用。 对于主备,如果主机故障,那么只需要直接将流量打到备机就可以,但是对于一主多从,还需要将从库连接到主库上。 对于切换的操作&a…...
SQLite数据库的性能问题并不是单纯地由数据量的大小决定的,而是受到多种因素的综合影响。以下是一些可能导致SQLite性能问题的因素
SQLite数据库的性能问题并不是单纯地由数据量的大小决定的,而是受到多种因素的综合影响。以下是一些可能导致SQLite性能问题的因素: 数据量:当SQLite数据库中的数据量增长到一定程度时,查询、插入和更新等操作可能会变得缓慢。这…...

Blender怎么样启动默认移动和Cavity效果
在使用Blender的过程中,有一些特殊的技巧很重要。 比如默认地设置blender打开时,就是移动物体,这样怎么样设置的呢? 需要在界面里打开下面的菜单: 这样就找到默认设置的地方,把下面的移动勾选起来,这样点…...
Android 解决TextView多行滑动与NestedScrollView嵌套滑动冲突的问题
关键计算地方: 1.当前是上滑动还是下滑动(相对于屏幕) ,使用ev.getRawY()获得当前滑动位置在屏幕哪个地方 2. 计算文本客滑动到哪里即可停止, (行高*总文本行数)- (行高 * 最多显示行数) int sum getLineHeight() * getLineCount() - getLineHeight() * getMaxLines(); …...
Laravel 开发Api规范
一,修改时区 配置 config/app.php 文件 // 时区修改,感觉两者皆可,自己根据实际情况定义 timezone > PRC, // 大陆时间二,设置 Accept 头中间件 accept头即为客户端请求头,做成中间件来使用。Accept 决定了响应返…...

蓝色wordpress外贸建站模板
蓝色wordpress外贸建站模板 https://www.mymoban.com/wordpress/7.html...

windos环境,使用docker容器运行项目的,新增外部访问地址配置
对于运行在 Docker 容器中的项目,你需要在容器内部编辑 resolv.conf 文件。以下是一种常见的方法: 进入正在运行的 Docker 容器:docker exec -it [container_id] bash其中 [container_id] 是你正在运行的 Docker 容器的 ID。 在容器内部使…...
设计模式:生活中的组合模式
想象一下,你正在组织一个大型的家庭聚会。在这个聚会中,你需要准备各种菜肴,每个菜肴又包含不同的食材。你的目标是能够以统一的方式处理整个聚会的准备工作,不论是处理单个食材还是一整道菜肴。 在这个场景中,我们可…...
WPF OnStartup
在Windows Presentation Foundation (WPF)框架中,OnStartup 是 System.Windows.Application 类的一个受保护的虚方法,它是应用程序启动过程中的一个重要环节。当一个 WPF 应用程序启动时,其入口点通常是 App.xaml 文件和对应的后台代码文件 A…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...
前端工具库lodash与lodash-es区别详解
lodash 和 lodash-es 是同一工具库的两个不同版本,核心功能完全一致,主要区别在于模块化格式和优化方式,适合不同的开发环境。以下是详细对比: 1. 模块化格式 lodash 使用 CommonJS 模块格式(require/module.exports&a…...
算法刷题-回溯
今天给大家分享的还是一道关于dfs回溯的问题,对于这类问题大家还是要多刷和总结,总体难度还是偏大。 对于回溯问题有几个关键点: 1.首先对于这类回溯可以节点可以随机选择的问题,要做mian函数中循环调用dfs(i&#x…...
大模型真的像人一样“思考”和“理解”吗?
Yann LeCun 新研究的核心探讨:大语言模型(LLM)的“理解”和“思考”方式与人类认知的根本差异。 核心问题:大模型真的像人一样“思考”和“理解”吗? 人类的思考方式: 你的大脑是个超级整理师。面对海量信…...