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

算法笔记:并查集

一、什么是并查集

并查集的逻辑结构是一个包含N个元素的集合,如图:

我们将各个元素划分为若干个互不相交的子集,如图:

二、并查集的基本操作

(一)初始化

初始化可以先将每个子集指向自己

 //初始化int [] un=new int[10];for (int i = 0; i < un.length; i++) { //先使得每个子集指向子集un[i]=i;}
(二)Find操作

返回指定索引的根

//并查集查询public int find(int x){if (un[x]==x){  //如果当前并查集指向自己 那么直接返回当前值即可return x;}else { //如果不指向自己 则代表有可能有指向链 那么就递归寻找  直到找到最终的根节点return find(un[x]);}}

(三)Union操作
●合并操作即将一个根指向另一个指定节点
 

//合并 也就是使得i指向jpublic void merge(int i,int j){un[find(i)]=find(j);  // un[find(i)] 是指 如果i索引 有指向其他节点的话 那么肯定要遍历到最终指向的父节点 然后将父节点与指定索引值合并 没有指向的话那么就是直接使得当前位置i指向j}
(四)Union操作(路径压缩)
 //合并(压缩路径)public int union(int x){if (un[x]==x){ //代表此时已经是跟节点return x;}else {un[x]=union(un[x]); //使得每一个节点都指向该父节点 比如1—>2—>3   3是最终根节点 那么这样写的最终效果就是  1->3  2—>3  3->3return un[x]; //返回父节点}}

相关文章:

算法笔记:并查集

一、什么是并查集 并查集的逻辑结构是一个包含N个元素的集合&#xff0c;如图&#xff1a; 我们将各个元素划分为若干个互不相交的子集&#xff0c;如图&#xff1a; 二、并查集的基本操作 &#xff08;一&#xff09;初始化 初始化可以先将每个子集指向自己 //初始化int []…...

密码系统设计实验3-2

文章目录 《密码系统设计》实验实验项目实验三 密码模块实现4-6 学时实践要求&#xff08;30 分&#xff09; 《密码系统设计》实验 实验项目 实验序号实验名称实验学时数实验目的实验内容实验类型学生学习预期成果实验三密码模块实现6基于商用密码标准的密码模块的实现实现简…...

Spring Boot 与 Spring Cloud Alibaba 版本兼容对照

版本选择要点 Spring Boot 3.x 与 Spring Cloud Alibaba 2022.0.x Spring Boot 3.x 基于 Jakarta EE&#xff0c;javax.* 更换为 jakarta.*。 需要使用 Spring Cloud 2022.0.x 和 Spring Cloud Alibaba 2022.0.x。 Alibaba 2022.0.x 对 Spring Boot 3.x 的支持在其发行说明中…...

SVD 奇异值分解

SVD 是一种矩阵分解和降维的算法&#xff0c;通过分解矩阵找到奇异值&#xff0c;奇异值越大代表特征越重要。公式如下 A U Σ V T A U \Sigma V^T AUΣVT U : 左矩阵 ( m \times m ) Σ \Sigma Σ: 对角奇异值矩阵V&#xff1a;右矩阵( n \times n ) Sklearn 实现 S…...

C++设计模式-享元模式

动机(Motivation) 在软件系统采用纯粹对象方案的问题在于大量细粒度的对象会很快充斥在系统中&#xff0c;从而带来很高的运行时代价——主要指内存需求方面的代价。如何在避免大量细粒度对象问题的同时&#xff0c;让外部客户程序仍然能够透明地使用面向对象的方式来进行操作…...

AI加持,华为全屋智能品牌升级为“鸿蒙智家”

1.传统智能家居的困境&#xff1a;从便利到繁琐 近年来&#xff0c;智能家居因其便捷性和科技感受到消费者的青睐。然而&#xff0c;随着用户需求的多样化&#xff0c;传统智能家居的弊端逐渐显现&#xff1a; 设备连接复杂&#xff0c;品牌间兼容性不足&#xff0c;用户不得不…...

洛谷刷题之p1631

序列合并 题目入口 题目描述 有两个长度为 N N N 的单调不降序列 A , B A,B A,B&#xff0c;在 A , B A,B A,B 中各取一个数相加可以得到 N 2 N^2 N2 个和&#xff0c;求这 N 2 N^2 N2 个和中最小的 N N N 个。 输入格式 第一行一个正整数 N N N&#xff1b; 第二…...

uniapp前端开发,基于vue3,element plus组件库,以及axios通讯

简介 UniApp 是一个基于 Vue.js 的跨平台开发框架&#xff0c;旨在通过一次开发、编译后运行在多个平台上&#xff0c;如 iOS、Android、H5、以及小程序&#xff08;微信小程序、支付宝小程序、百度小程序等&#xff09;等。UniApp 为开发者提供了统一的开发体验&#xff0c;使…...

在Unity中实现物体动画的完整流程

在Unity中&#xff0c;动画是游戏开发中不可或缺的一部分。无论是2D还是3D游戏&#xff0c;动画都能为游戏增添生动的视觉效果。本文将详细介绍如何在Unity中为物体添加动画&#xff0c;包括资源的准备、播放组件的添加、动画控制器的创建以及动画片段的制作与调度。 1. 准备动…...

【云计算网络安全】解析 Amazon 安全服务:构建纵深防御设计最佳实践

文章目录 一、前言二、什么是“纵深安全防御”&#xff1f;三、为什么有必要采用纵深安全防御策略&#xff1f;四、以亚马逊云科技为案例了解纵深安全防御策略设计4.1 原始设计缺少安全策略4.2 外界围栏构建安全边界4.3 访问层安全设计4.4 实例层安全设计4.5 数据层安全设计4.6…...

【Andriod ADB基本命令总结】

笔者工作当中遇到安卓机器的数据访问和上传,特来简单总结一下常用命令。 1、ADB命令简介与安装 简介: ADB (Android Debug Bridge) 是一个强大的命令行工具,用于与 Android 设备进行交互,常用于开发、调试、测试以及设备管理等操作。它是 Android 开发工具包(SDK)的一部…...

ChatGPT如何辅助academic writing?

今天想和大家分享一篇来自《Nature》杂志的文章《Three ways ChatGPT helps me in my academic writing》&#xff0c;如果您的日常涉及到学术论文的写作&#xff08;writing&#xff09;、编辑&#xff08;editing&#xff09;或者审稿&#xff08; peer review&#xff09;&a…...

Day 27 贪心算法 part01

贪心算法其实就是没有什么规律可言,所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其规律, 没有思路就立刻看题解。 基本贪心的题目 有两个极端,要不就是特简单,要不就是死活想不出来。 学完贪心之后再去看动态规划,就会了解贪心和动规的区别。…...

使用Python实现目标追踪算法

引言 目标追踪是计算机视觉领域的一个重要任务&#xff0c;广泛应用于视频监控、自动驾驶、机器人导航、运动分析等多个领域。目标追踪的目标是在连续的视频帧中定位和跟踪感兴趣的物体。本文将详细介绍如何使用Python和OpenCV实现一个基本的目标追踪算法&#xff0c;并通过一…...

某科技研发公司培训开发体系设计项目成功案例纪实

某科技研发公司培训开发体系设计项目成功案例纪实 ——建立分层分类的培训体系&#xff0c;加强培训跟踪考核&#xff0c;促进培训成果实现 【客户行业】科技研发行业 【问题类型】培训开发体系 【客户背景】 某智能科技研发公司是一家专注于智能科技、计算机软件技术开发与…...

如何通过高效的缓存策略无缝加速湖仓查询

引言 本文将探讨如何利用开源项目 StarRocks 的缓存策略来加速湖仓查询&#xff0c;为企业提供更快速、更灵活的数据分析能力。作为 StarRocks 社区的主要贡献者和商业化公司&#xff0c;镜舟科技深度参与 StarRocks 项目开发&#xff0c;也为企业着手构建湖仓架构提供更多参考…...

Linux V4L2框架介绍

linux V4L2框架介绍 V4L2框架介绍 V4L2&#xff0c;全称Video for Linux 2&#xff0c;是Linux操作系统下用于视频数据采集设备的驱动框。它提供了一种标准化的方式使用户空间程序能够与视频设备进行通信和交互。通过V4L2接口&#xff0c;用户可以方便地实现视频图像数据的采…...

【前端】JavaScript 中 arguments、类数组与数组的深入解析

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: 前端 文章目录 &#x1f4af;前言&#x1f4af;什么是 arguments 对象2.1 arguments 的定义2.2 arguments 的特性2.3 使用场景 &#x1f4af;深入了解 arguments 的结构3.1 arguments 的内部结构arguments 的关键属性…...

Android 布局菜单或按钮图标或Menu/Item设置可见和不可见

设置可见和不可见 即 设置 显示和隐藏&#xff1b;是双向设置&#xff1b;什么情况显示&#xff0c;什么情况隐藏分判断的条件 它不同于删除和屏蔽&#xff0c;删除和屏蔽&#xff0c;覆盖是单向的&#xff0c;不可逆转的。它间接等于单向的隐藏&#xff01;&#xff01;&…...

|| 与 ??的区别

?? : 空值合并运算符&#xff0c; 用于在左侧操作数为 null 或 undefined 时返回右侧操作数 let name null // null 或者 undefinedlet defaultName defaultNamelet displayName name ?? defaultNameconsole.log(displayName) // defaultName || : 逻辑或&#xff0c;…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...