当前位置: 首页 > 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;…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...