并查集(基础+带权以及可撤销并查集后期更新)
并查集
并查集是一种图形数据结构,用于存储图中结点的连通关系。
每个结点有一个父亲,可以理解为“一只伸出去的手”,会指向另一个点,初始时指向自己。一个点的根节点是该点的父亲的父亲的..的父亲,直到某个点的父亲是自己(根)。
当两个点的根相同时,我们就说他们时同一类,或者是连通的。
如下:7,5,1,3,6的根都是3,所以他们是连通的。
2,4是连通的,而2,6不连通,因为他们的根不同。
找根的方法
如果当前点不是根,就返回父亲的根。否则就是自己
用递归的方法实现
int find(int x)
{
if(pre[x]==x)retrun x;
return find(pre[x]);
}
并查集的合并
在并查集中所有的操作都在根上,假如我要使x和y两个点合并,我们只需要将find(x)指向find(y)或者find(y)指向find(x);
pre[find(x)]=find(y);
假如我们要合并4和6两点,我们只需要将2指向3或将3指向2.
路径压缩
找根函数的复杂度最坏情况下会达到O(n),如果查询次数较多的话效率将会非常低下。
我们可以在找根的过程中,将父亲指向根,从而实现路径压缩,这样可以使得找根的总体时间的复杂度为O(log n)。如下图,执行一次root(7)之后,沿途的点都会直接指向根3
int find(int x){
return pre[x]=(pre[x]==x?x:find(pre[x]));//当前的这个点是否是根,是根的话直接输出x不是根的话,去寻中这个根
}
例题
蓝桥幼儿园
题目描述
蓝桥幼儿园的学生是如此的天真无邪,以至于对他们来说,朋友的朋友就是自己的朋友。
小明是蓝桥幼儿园的老师,这天他决定为学生们举办一个交友活动,活动规则如下:
小明会用红绳连接两名学生,被连中的两个学生将成为朋友。
小明想让所有学生都互相成为朋友,但是蓝桥幼儿园的学生实在太多了,他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你,请你帮忙写程序判断某两个学生是否为朋友(默认自己和自己也是朋友)。
输入描述
第 11 行包含两个正整数N,M,其中 N 表示蓝桥幼儿园的学生数量,学生的编号分别为1∼N。
之后的第2∼M+1 行每行输入三个整数op,x,y:
- 如果 op=1,表示小明用红绳连接了学生 x 和学生 y 。
- 如果 op=2,请你回答小明学生 x 和 学生 y 是否为朋友。
输出描述
对于每个op=2 的输入,如果 x 和 y 是朋友,则输出一行 YES
,否则输出一行 NO
。
输入输出样例
示例 1
输入
5 5
2 1 2
1 1 3
2 1 3
1 2 3
2 1 2
输出
NO
YES
YES
代码
package chsi;
import java.util.*;
public class chapter1 {static int []pre;//定义一个数组表示每个结点的根是指向谁的public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();pre=new int[n];//初始化prefor(int i=0;i<n;i++) pre[i]=i;//初始根都是指向它本身for(int i=0;i<m;i++) {int op=scan.nextInt();int x=scan.nextInt()-1;int y=scan.nextInt()-1;if(op==1) {union(x,y);}else {x=find(x);y=find(x);if(x==y) {System.out.println("YES");}else System.out.println("No");}}}public static int find(int x) {if(pre[x]!=x) {pre[x]=find(pre[x]);}//表示当前结点不是我们的根节点return pre[x];}//先写一个find查询,路径压缩的方式public static void union(int x,int y) {x=find(x);y=find(y);if(x!=y) {pre[x]=y;}return;}}
相关文章:
并查集(基础+带权以及可撤销并查集后期更新)
并查集 并查集是一种图形数据结构,用于存储图中结点的连通关系。 每个结点有一个父亲,可以理解为“一只伸出去的手”,会指向另一个点,初始时指向自己。一个点的根节点是该点的父亲的父亲的..的父亲,直到某个点的父亲…...
基于 Java 的数据结构和算法 (不定期更新)
JavaIsBestLang 数据结构 Collection 是 Java 中的接口,被多个泛型容器接口所实现。在这里,Collection 是指代存放对象类型的数据结构。 ArrayList 函数名功能size()返回 this 的长度add(Integer val)在 this 尾部插入一个元素add(int idx, Integer …...
考研回忆录【二本->211】
备考时长差不多快一年半,从22年的11月底开始陆陆续续地准备考研,因为开始的早所以整个备考过程显得压力不是很大,中途还去一些地方旅游,我不喜欢把自己绷得太紧。虽然考的不是很好,考完我甚至都没准备复试,…...
【XCPC笔记】2023 (ICPC) Jiangxi Provincial Contest——ABCIJKL 做题记录
补题 赛后gym练习及补题,gym链接:2023 (ICPC) Jiangxi Provincial Contest – Official Contest 另外,D题我也打算找机会学习写下,C题的博弈论还需要好好理解,感觉都是比较有趣的数学问题 补题顺序如下 补题L [Zhang …...
猫头虎分享已解决Bug || **URLError (URL错误)** 全方位解析
博主猫头虎的技术世界 🌟 欢迎来到猫头虎的博客 — 探索技术的无限可能! 专栏链接: 🔗 精选专栏: 《面试题大全》 — 面试准备的宝典!《IDEA开发秘籍》 — 提升你的IDEA技能!《100天精通鸿蒙》 …...
如何使用极狐GitLab 启用自动备份功能
本文作者:徐晓伟 GitLab 是一个全球知名的一体化 DevOps 平台,很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab 是 GitLab 在中国的发行版,专门为中国程序员服务。可以一键式部署极狐GitLab。 本文主要讲述了如何极狐GitLab 自…...
HTML/XML转义字符对照
特殊字符转义表 字符十进制转义字符""&&<<<>>>不断开空格(non-breaking space) 最常用的转义字符列表 显示说明实体名称十进制编号半方大的空白 全方大的空白 不断行的空白格 <小于<<>大于&g…...
设计模式:组合模式示例
组合模式的典型例子通常涉及到树形结构的处理,下面是几个形象且易于理解的例子: 文件系统 在文件系统中,目录可以包含文件或者其他目录,但是从用户的角度来看,目录和文件都可以被“打开”或者“获取大小”。这里的目…...
普通情况和高并发时,Redis缓存和数据库怎么保持一致?
普通情况和高并发时,Redis缓存和数据库怎么保持一致? 普通情况思路 高并发时思路 Q:缓存和数据库怎么保持一致? A:绝对不可能保持一致的,在实际业务开发中,有一些方案可以做取舍。 实际业务中&a…...
Django -- 自动化测试
概述 测试是一种例行的、不可缺失的工作,用于检查你的程序是否符合预期。 测试可以划分为不同的级别。一些测试可能专注于小细节(比如某一个模型的方法是否会返回预期的值?), 一些测试则专注于检查软件的整体运行是否…...
NodeJS 在Windows / Mac 上实现多版本控制
NodeJS 的多版本控制 本文介绍一下在 windows/MacOS 上 如何 切换和使用多个版本的 NodeJS。 Windows 本小节介绍一下在windows上管理不同版本的NodeJS。 nvm-windows 工具 nvm-windows 是在 windows 上管理 NodeJS 版本的一个工具。 它可以很方便的 下载、移除、查看、切…...
Web3 游戏周报(3.24-3.30)
【3.24-3.30】Web3 游戏行业动态: Web3 开发平台 Mirror World 在 Solana 上推出首个游戏 rollup 链 NFT 卡牌游戏 Parallel 完成 3,500 万美元融资,Solana Ventures 等参投 加密游戏开发公司 Gunzilla Games 完成 3,000 万美元融资 Telegram 游戏 No…...
算法思想1. 分治法2. 动态规划法3. 贪心算法4. 回溯法
目录 递归和动态的区别:空间和时间复杂度之争 递归空间复杂度低;动态时间复杂度第低...
SpringBoot+ECharts+Html 地图案例详解
1. 技术点 SpringBoot、MyBatis、thymeleaf、MySQL、ECharts 等 此案例使用的地图是在ECharts社区中查找的:makeapie echarts社区图表可视化案例 2. 准备条件 在mysql中创建数据库echartsdb,数据库中创建表t_location_count表,表中设置两个…...
达梦数据库 优化
谁进行优化?优化什么? 优化不能仅从数据库方面考虑,比如,在存储达到数据库极限、应用涉及人员设计的代码稀巴烂的情况下,进行调优就是杯水车薪的效果。 涉及到优化人员: 数据库管理员应用程序架构师应用…...
数据如何才能供得出、流得动、用得好、还安全
众所周知,数据要素已经列入基本生产要素,同时成立国家数据局进行工作统筹。目前数据要素如何发挥其价值,全国掀起了一浪一浪的热潮。 随着国外大语言模型的袭来,国内在大语言模型领域的应用也大放异彩,与此同时&#x…...
idea开发 java web 酒店推荐系统bootstrap框架开发协同过滤算法web结构java编程计算机网页
一、源码特点 java 酒店推荐推荐系统是一套完善的完整信息系统,结合java web开发和bootstrap UI框架完成本系统 采用协同过滤算法进行推荐 ,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式…...
Linux——线程控制
目录 前言 一、线程创建 1.创建线程 2.线程传递结构体 3.创建多线程 4.收到信号的线程 二、线程终止 三、线程等待 四、线程分离 五、取消线程 六、线程库管理的原理 七、站在语言角度理解pthread库 八、线程的局部存储 前言 前面我们学习了线程概念和线程创建&…...
【Leetcode 347】,前k个高频元素,小根堆的调整
参考题解 题目:给定一个数组,输出 前k个高频元素。 思路: 遍历数组,建立小根堆(小根堆的元素是元组(num,freq),排序规则是每个元素的频率)。 下面使用数组‘heap’&…...
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
本文涉及的知识点 图论 分类讨论 本题同解 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 LeetCode3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 …...
浅谈Yum 安装和 源码安装
浅谈Yum 安装和 源码安装 本文所叙述的Linux系统是基于RedHat发行版的CentOS7 yum安装 1. 前言 我们知道在Windows上下载的安装包后缀是 .exe ,与之对应的 在 Linux下的安装包的后缀是 .rpm rpm (Red Hat Package Manager) 是红帽软件包管理器 我们在Windows电脑…...
JavaEE初阶Day 3:多线程(1)
目录 Day 3:多线程(1)1. 线程1.1 引入线程的原因1.2 线程的定义1.3 为何线程更轻量1.4 问题 2. 多线程代码2.1 继承Thread重写run2.2 通过实现Runnable接口创建线程2.3 针对2.1的变形使用匿名内部类2.4 针对Runnable创建匿名内部类2.5 使用la…...
gutil140.dll是什么?gutil140.dll无法继续执行的解决方法
gutil140.dll文件是一个动态链接库(DLL)文件,通常与Microsoft Visual Studio 2015相关联。 gutil140.dll是开发过程中使用的工具函数集合,它辅助开发人员执行常见的编程任务,如文件操作、内存分配和字符串处理等。这个…...
在CentOS 7上安装Python 3.7.7
文章目录 一、实战步骤1. 安装编译工具2. 下载Python 3.7.7安装包3. 上传Python 3.7.7安装包4. 解压缩安装包5. 切换目录并编译安装6. 配置Python环境变量7. 使配置生效8. 验证安装是否成功 二、实战总结 一、实战步骤 1. 安装编译工具 在终端中执行以下命令 yum -y groupin…...
基于SpringBoot Vue宠物领养系统
一、📝功能介绍 基于SpringBoot Vue宠物领养系统 角色:管理员、用户 当游客打开系统的网址后,首先看到的就是首页界面。在这里,游客能够看到宠物领养救助平台的导航条显示首页、宠物招领、宠物认领、 宠物论坛、宠物资讯、后台管…...
ip命令
ip a 也是ip addr简写 [rootlocalhost ~]# ip a 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00inet 127.0.0.1/8 scope host lovalid_lft forever preferred_lft…...
【Kaggle】练习赛《鲍鱼年龄预测》(上)
前言 上一篇文章,讲解了《肥胖风险的多类别预测》机器学习方面的文章,主要是多分类算法的运用,本文是一个回归的算法,本期是2024年4月份的题目《Regression with an Abalone Dataset》即《鲍鱼年龄预测》,在此分享高手…...
Ruby 之交租阶段信息生成
题目 我看了一下,这个题目应该不是什么机密,所以先放上来了。大概意思是根据合同信息生成交租阶段信息。 解答 要求是要使用 Ruby 生成交租阶段信息,由于时间比较仓促,变量名那些就用得随意了些。要点主要有下面这些:…...
RUST语言值所有权之内存复制与移动
1.RUST中每个值都有一个所有者,每次只能有一个所有者 String::from函数会为字符串hello分配一块内存 内存示例如下: 在内存分配前调用s1正常输出 在分配s1给s2后调用报错 因为s1分配给s2后,s1的指向自动失效 s1被move到s2 s1自动释放 字符串克隆使用...
【Django学习笔记(三)】BootStrap介绍
BootStrap介绍 前言正文1、BootStrap 快速了解2、初识BootStrap2.1 下载地址2.2 创建目录2.3 引入BootStrap2.4 使用BootStrap 3、BootStrap 组件&样式3.1 导航条3.2 栅格系统3.3 container3.3.1 container3.3.2 container-fluid 3.4 面板3.5 媒体对象3.6 分页3.7 图标3.7.…...
wordpress 主题腾讯cdc/温州seo优化公司
目录版本整形数组浮点型数组嵌套列表构成的多维数组,内层的列表被当作二维数组的行创建一个长度为10的数组,数组的值都是0创建一个长度为10的数组,数组的值都是1创建一个35的浮点型数组,数组的值都是3.14创建一个数组,…...
城市建设网站设计/百度ai智能写作工具
在一个类中创建另外一个类,叫做成员内部类。这个成员内部类可以静态的(利用static关键字修饰),也可以是非静态的。由于静态的内部类在定义、使用的时候会有种种的限制。所以在实际工作中用到的并不多。 在开发过程中ÿ…...
html网站用什么空间/郑州关键词seo
创建自定义对象选项卡 创建自定义对象选项卡,让您的用户可以访问应用程序中的自定义对象数据和记录。自定义对象选项卡仅在应用程序级别可用,在子选项卡应用程序上不可用。自定义对象选项卡的外观和功能与标准选项卡相似。 所需的 EDITION 和用户权限&a…...
沈阳网站建设 景乔科技/最近一周新闻
抖音问我 有个小伙伴问了一个问题:“在B站,有几乎所有机构的最新的培训视频,明明可以免费学,为什么会有人花2万块钱,去培训机构学四个月?” 为什么培训机构敢把视频放在B站? 但事实上操作起来&a…...
婚礼婚庆网站建设需求分析/百度店铺
错误代码:SELECT列表1055表达式#1是不是在GROUP BY子句中包含非聚合列这并不功能依赖于GROUP BY子句中的列; 这是不符合的SQL_MODE ONLY_FULL_GROUP_BY 我试图查询一个复杂的SQL查询与联接,团体等,并升级MySQL后组停止工作。 为了…...
阜宁网站建设服务商/关键词优化需要从哪些方面开展
[MySQL 5.6] MySQL 5.6 online ddl 使用、测试及关键函数栈 http://mysqllover.com/?p547本文主要分为三个部分,第一部分是看文档时的笔记;第二部分使用sysbench简单测试了下性能损耗;第三部分阐述了关键函数栈,但未做深入前言 O…...