当前位置: 首页 > news >正文

[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 句话有的是真的,有的是假的。

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

  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≤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&#xff0c;这三类动物的食物链构成了有趣的环形。 A 吃 B&#xff0c;B 吃 C&#xff0c;C 吃 A。 现有 N 个动物&#xff0c;以 1∼N 编号。 每个动物都是 A,B,C 中的一种&#xff0c;但是我们并不知道它到底是哪一种。 有人用两种说法对这 N…...

深入理解Transformer的位置编码机制

Transformer架构由于其独特的设计&#xff0c;不像传统的循环神经网络&#xff08;RNN&#xff09;或卷积神经网络&#xff08;CNN&#xff09;&#xff0c;它无法自然地处理序列数据中的顺序信息。为了使模型能够理解序列中各元素的位置关系&#xff0c;Transformer引入了一种…...

10分钟上手:MySQL8的Json格式字段使用总结干货

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

OpenCV 4.9基本绘图

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

显示器and拓展坞PD底层协商

简介&#xff1a; PD显示器或者PD拓展坞方案中&#xff0c;连接显示设备的Type-C端口主要运行在DRP模式&#xff0c;在此模式下可以兼容Source&#xff08;显卡&#xff09;、Sink&#xff08;信号器&#xff09;、DRP&#xff08;手机、电脑&#xff09;模式的显示设备。 Sou…...

如何利用Flutter将应用成功上架至iOS平台:详细指南

引言 &#x1f680; Flutter作为一种跨平台的移动应用程序开发框架&#xff0c;为开发者提供了便利&#xff0c;使他们能够通过单一的代码库构建出高性能、高保真度的应用程序&#xff0c;同时支持Android和iOS两个平台。然而&#xff0c;完成Flutter应用程序的开发只是第一步…...

【运输层】网络数据报协议 UDP

目录 1、UDP 的特点 2、UDP 的首部格式 UDP 只在 IP 协议之上增加了很少的一些功能&#xff0c;比如复用、分用以及差错检测等。 1、UDP 的特点 UDP是无连接的&#xff0c;即发送数据之前不需要建立连接&#xff0c;因此减少了开销和发送数据之前的时延。 UDP使用尽最大努力…...

数据结构(初阶):顺序表实战通讯录

前言 数据结构&#xff08;初阶&#xff09;第一节&#xff1a;数据结构概论-CSDN博客 数据结构&#xff08;初阶&#xff09;第二节&#xff1a;顺序表-CSDN博客 本文将以C语言和顺序表实现通讯录基础管理&#xff0c;实现功能包括增、删、改、查等&#xff0c;在实现相关功能…...

Outlook会议邀请邮件在答复后就不见了

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

【C++】list模拟实现

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

ETL工具-nifi干货系列 第八讲 处理器PutDatabaseRecord 写数据库(详细)

1、本节通过一个小例子来讲解下处理器PutDatabaseRecord&#xff0c;该处理器的作用是将数据写入数据库。 如下流程通过处理器GenerateFlowFile 生成数据&#xff0c;然后通过处理器JoltTransformJSON转换结构&#xff0c;最后通过处理器PutDatabaseRecord将数据写入数据库。如…...

【MySQL】如何判断一个数据库是否出问题

在实际的应用中&#xff0c;其实大多数是主从结构。而采用主备&#xff0c;一般都需要一定的费用。 对于主备&#xff0c;如果主机故障&#xff0c;那么只需要直接将流量打到备机就可以&#xff0c;但是对于一主多从&#xff0c;还需要将从库连接到主库上。 对于切换的操作&a…...

SQLite数据库的性能问题并不是单纯地由数据量的大小决定的,而是受到多种因素的综合影响。以下是一些可能导致SQLite性能问题的因素

SQLite数据库的性能问题并不是单纯地由数据量的大小决定的&#xff0c;而是受到多种因素的综合影响。以下是一些可能导致SQLite性能问题的因素&#xff1a; 数据量&#xff1a;当SQLite数据库中的数据量增长到一定程度时&#xff0c;查询、插入和更新等操作可能会变得缓慢。这…...

Blender怎么样启动默认移动和Cavity效果

在使用Blender的过程中&#xff0c;有一些特殊的技巧很重要。 比如默认地设置blender打开时&#xff0c;就是移动物体&#xff0c;这样怎么样设置的呢&#xff1f; 需要在界面里打开下面的菜单: 这样就找到默认设置的地方&#xff0c;把下面的移动勾选起来&#xff0c;这样点…...

Android 解决TextView多行滑动与NestedScrollView嵌套滑动冲突的问题

关键计算地方: 1.当前是上滑动还是下滑动(相对于屏幕) ,使用ev.getRawY()获得当前滑动位置在屏幕哪个地方 2. 计算文本客滑动到哪里即可停止, (行高*总文本行数)- (行高 * 最多显示行数) int sum getLineHeight() * getLineCount() - getLineHeight() * getMaxLines(); …...

Laravel 开发Api规范

一&#xff0c;修改时区 配置 config/app.php 文件 // 时区修改&#xff0c;感觉两者皆可&#xff0c;自己根据实际情况定义 timezone > PRC, // 大陆时间二&#xff0c;设置 Accept 头中间件 accept头即为客户端请求头&#xff0c;做成中间件来使用。Accept 决定了响应返…...

蓝色wordpress外贸建站模板

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

windos环境,使用docker容器运行项目的,新增外部访问地址配置

对于运行在 Docker 容器中的项目&#xff0c;你需要在容器内部编辑 resolv.conf 文件。以下是一种常见的方法&#xff1a; 进入正在运行的 Docker 容器&#xff1a;docker exec -it [container_id] bash其中 [container_id] 是你正在运行的 Docker 容器的 ID。 在容器内部使…...

设计模式:生活中的组合模式

想象一下&#xff0c;你正在组织一个大型的家庭聚会。在这个聚会中&#xff0c;你需要准备各种菜肴&#xff0c;每个菜肴又包含不同的食材。你的目标是能够以统一的方式处理整个聚会的准备工作&#xff0c;不论是处理单个食材还是一整道菜肴。 在这个场景中&#xff0c;我们可…...

WPF OnStartup

在Windows Presentation Foundation (WPF)框架中&#xff0c;OnStartup 是 System.Windows.Application 类的一个受保护的虚方法&#xff0c;它是应用程序启动过程中的一个重要环节。当一个 WPF 应用程序启动时&#xff0c;其入口点通常是 App.xaml 文件和对应的后台代码文件 A…...

idea大量爆红问题解决

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

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过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 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&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 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...