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

并查集模板:食物链详解


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {static int N = 50010;static int n,m; //n个动物,m局判断static int[] p = new int[N];    //p[i]是i的根节点static int[] d = new int[N];    //d[i]表示i到其父节点的距离,通过find函数会路径压缩变成到根节点的具体static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));public static int find(int x){  //返回根节点if (p[x] != x){ //如果你要找的节点不仅仅只有自己,就要往上找,去找自己的祖宗//先递归得到根节点//假设此时已经形成了一段树,p[x] = N,从p[1]开始找,一直让x增到N即p[N] = N;int t = find(p[x]);//调用结束的x是 根节点N - 1,根节点的d[N]不需要更新//从根节点开始的孩子开始,回溯,路径压缩更新该节点到根节点的距离//再调用find方法前,会设置d[p[x]]为1d[x] += d[p[x]];p[x] = t;   //最后再更新find(x)~find(N-1)的父节点为N}//最后返回根节点Nreturn p[x];}public static void main(String[] args) throws IOException {String[] init = in.readLine().split(" ");n = Integer.parseInt(init[0]);m = Integer.parseInt(init[1]);//初始化并查集for (int i = 0; i < n; i++) {p[i] = i;}int res = 0;    //说谎话的个数while (m-- > 0){init = in.readLine().split(" ");int t= Integer.parseInt(init[0]);int x= Integer.parseInt(init[1]);int y= Integer.parseInt(init[2]);if (x > n || y > n) res ++;else {int px = find(x),py = find(y);  //找到这两个树的根节点if (t == 1)//同类{//作为同类如果再一个集合关系里,他们的等级相差%3!= 0if (px == py &&  (d[x] - d[y]) % 3 != 0) res ++;else if (px != py){ //这里要用else if 不能直接用else,同类也可能走到这//不同类,把它俩放在一个集合里p[px] = py; //py作为px的父亲d[px] = (d[y] - d[x]) % 3;}}else {//吃,如果在一个集合里,同类的化,x 吃 y//x在%3的情况下要比y多一个等级if (px == py && (d[x] - d[y] - 1) % 3 != 0) res ++;else if (px != py){//不同一个集合,把他们放在一起,x比y高一个等级p[px] = p[y];//在调用find之前会先走这里,把根节点的到它的孩子距离设置成1d[px] = (d[y] - d[x] + 1) % 3;}}}}System.out.println(res);}
}

相关文章:

并查集模板:食物链详解

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;public class Main {static int N 50010;static int n,m; //n个动物,m局判断static int[] p new int[N]; //p[i]是i的根节点static int[] d new int[N]; //d[i]表示i到…...

使用WAF防御网络上的隐蔽威胁之反序列化攻击

​ 什么是反序列化 反序列化是将数据结构或对象状态从某种格式转换回对象的过程。这种格式通常是二进制流或者字符串&#xff08;如JSON、XML&#xff09;&#xff0c;它是对象序列化&#xff08;即对象转换为可存储或可传输格式&#xff09;的逆过程。 反序列化的安全风险 反…...

05. 交换机的基本配置

文章目录 一. 初识交换机1.1. 交换机的概述1.2. Ethernet_ll格式1.3. MAC分类1.4. 冲突域1.5. 广播域1.6. 交换机的原理1.7. 交换机的3种转发行为 二. 初识ARP2.1. ARP概述2.2. ARP报文格式2.3. ARP的分类2.4. 免费ARP的作用 三. 实验专题3.1. 实验1&#xff1a;交换机的基本原…...

yolo将标签数据打到原图上形成目标框

第一章 目标&#xff1a;为了查看自己在标注标签时是否准确&#xff0c;写了这段代码来将标注的框打到原图上 第二章 步骤&#xff1a;进行反归一化得到坐标画出矩形框 第二行是目标图片对应的txt,第三行是目标图片 第三章 全部代码如下&#xff1a; import cv2 import …...

002-00-02【大红ai源码】dolphinscheduler3.2.0 源码环境搭建------by孤山村头王大爷家女儿大红

【ai阅读源码-dolphinscheduler】 DolphinScheduler 开发手册1、软件要求2、克隆代码库3、编译打包4、代码风格5、新建数据库&#xff0c;导入元数据。6&#xff0c; 启动后端6.1 启动api-server 6.2 启动master-server6.3 启动worker-server 7 启动前端 DolphinScheduler 开发…...

python-自动化篇-运维-监控-如何使⽤Python处理和解析⽇志⽂件?-实操记录

文章目录 1. 选择日志文件格式&#xff1a; 确定要处理的日志文件的格式。不同的日志文件可能具有不同的格式&#xff0c;如文本日志、CSV、JSON、XML等。了解日志文件的格式对解析⾮常重要。2. 打开日志文件&#xff1a; 使⽤Python的文件操作功能打开日志文件&#xff0c;以便…...

代码随想录算法训练营DAY6 | 哈希表(1)

DAY5休息一天&#xff0c;今天重启~ 哈希表理论基础&#xff1a;代码随想录 Java hash实现 &#xff1a;java 哈希表-CSDN博客 一、LeetCode 242 有效的字母异位词 题目链接&#xff1a;242.有效的字母异位词 思路&#xff1a;设置字典 class Solution {public boolean isAnag…...

【嵌入式学习】C++QT-Day3-C++基础

笔记 见我的博客&#xff1a;https://lingjun.life/wiki/EmbeddedNote/19Cpp 作业 设计一个Per类&#xff0c;类中包含私有成员:姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员:成绩、Per类对象p1&#xff0c;设计这两个类的构造函…...

表贴式PMSM的直接转矩控制(DTC)MATLAB仿真模型

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 模型简介 表贴式PMSM的直接转矩控制(DTC),直接使用滞环控制对转矩和磁链进行控制&#xff0c;相对于传统的FOC控制而言&#xff0c;其不需要进行解耦变换&#xff0c;在此次的有以下几点需要注意&#xff1a…...

详解OpenHarmony各部分文件在XR806上的编译顺序

大家好&#xff0c;今天我们来谈一谈编程时一个很有趣的话题——编译顺序。我知道&#xff0c;一提到编译可能大家会感到有点儿头疼&#xff0c;但请放心&#xff0c;我不会让大家头疼的。我们要明白&#xff0c;在开始写代码之前&#xff0c;了解整个程序的编译路径是十分有必…...

【美团】无人机-大数据开发工程师

更新时间&#xff1a;2024/01/29 工作地点&#xff1a;北京市 事业群&#xff1a;到家事业群 工作经验&#xff1a;3年 部门介绍 为了更好地提升城市即时配送的效率与体验&#xff0c;美团于2017年启动了无人机配送服务的探索&#xff0c;通过科技创新推动履约工具变革&#x…...

微服务系统设计:横向扩展和纵向扩展的对比

微服务扩展性&#xff1a;水平扩展 vs 垂直扩展 特点水平扩展垂直扩展扩展单位增加微服务实例增加单个实例的资源 (CPU&#xff0c;内存)方向向外&#xff0c;增加节点向上&#xff0c;增加单个节点的资源复杂性随着实例数量的增加&#xff0c;管理难度更大管理更简单&#xf…...

Java基于SpringBoot+Vue的网上超市管理系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

HTTP中POST、GET、PUT、DELETE方式的区别

GET请求会向数据库发索取数据的请求&#xff0c;从而来获取信息&#xff0c;该请求就像数据库的select操作一样&#xff0c;只是用来查询一下数据&#xff0c;不会修改、增加数据&#xff0c;不会影响资源的内容&#xff0c;即该请求不会产生副作用。无论进行多少次操作&#x…...

77.Go中interface{}判nil的正确姿势

文章目录 一&#xff1a;interface{}简介二、interface{}判空三&#xff1a;注意点四&#xff1a;实际案例 一&#xff1a;interface{}简介 在go中的nil只能赋值给指针、channel、func、interface、map或slice类型的变量 interface 是否根据是否包含有 method&#xff0c;底层…...

ES实战回顾

1、你用的集群节点情况&#xff1f; 一个ES集群&#xff0c;18个节点&#xff0c;其中3个主节点&#xff0c;15个数据节点&#xff0c;500G左右的索引数据量&#xff0c;没有单独的协调节点&#xff0c;它的每个节点都可以充当协调功能&#xff1b; 2、你们常用的索引有哪些&a…...

Mysql 删除数据

从数据表中删除数据使用DELETE语句&#xff0c;DELETE语句允许WHERE子句指定删除条件。DELETE语句基本语法格式如下&#xff1a; DELETE FROM table_name [WHERE <condition>]; table_name指定要执行删除操作的表&#xff1b;“[WHERE <condition>]”为可选参数&a…...

CSS设置单行文字水平垂直居中的方法

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>单行文字水平垂直居中</title><style>div {/* 给div设置宽高 */width: 400px;height: 200px;margin: 100px auto;background-color: red;/…...

数论与图论

数论&#x1f388; 筛质数 最普通的筛法O(nlogn)&#xff1a; void get_primes2(){for(int i2;i<n;i){if(!st[i]) primes[cnt]i;//把素数存起来for(int ji;j<n;ji){//不管是合数还是质数&#xff0c;都用来筛掉后面它的倍数st[j]true;}} } 诶氏筛法 O(nloglogn)&#…...

海外云手机三大优势

在全球化潮流下&#xff0c;企业因业务需求对海外手机卡等设备的需求不断攀升&#xff0c;推动了海外云手机业务的蓬勃发展。相较于自行置备手机设备&#xff0c;海外云手机不仅能够降低成本&#xff0c;还具备诸多优势&#xff0c;让我们深入探讨其中的三大黄金优势。 经济实惠…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...