[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…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...

python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...