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

算法篇 : 并查集

介绍

        英文名:union find set

        作用:合并集合,查询集合

        合并:将有直接关系的顶点放在一个集合里面

        查找:查询某个顶点所属的集合

        集合的标志:用祖先点的标号作为每个集合的标识

案例 

          如果说将下图的集合2合并至集合1

         那么应该让3的祖先为1,即:

 

实现流程

        1)对所有顶点标号,其祖先节点默认为自己

        2)合并:以两个点中祖先标号小的作为新祖先进行合并

        3)查找:查找点的祖先,并更新查找路径点的祖先

Java代码实现
//顶点类
public class Vertex {public Integer id;public Vertex(Integer id){this.id=id;}
}//并查集的操作类
public class UnionFindSetOperator {private List<Vertex>vertexs;    //所有顶点private List<List<Vertex>>connectVertexs;    //所有有直接关系的顶点private Map<Vertex,Vertex>ancestor;public UnionFindSetOperator(List<Vertex> vertexs, List<List<Vertex>> connectVertexs) {this.vertexs = vertexs;this.connectVertexs = connectVertexs;this.ancestor=new HashMap<>();//将所有顶点的祖先初始化默认设置为自己for(int i=0;i< vertexs.size();i++){ancestor.put(vertexs.get(i),vertexs.get(i));}//合并所有直接相连的顶点for(int i=0;i< connectVertexs.size();i++){Union(connectVertexs.get(i).get(0),connectVertexs.get(i).get(1));}}public void Union(Vertex vertex1,Vertex vertex2){Vertex ancestor1=Find(vertex1);Vertex ancestor2=Find(vertex2);//选取两个祖先id小的作为新祖先if(ancestor1.id<ancestor2.id)ancestor.put(vertex2,ancestor1);elseancestor.put(vertex1,ancestor2);}public Vertex Find(Vertex vertex){if(ancestor.get(vertex)!=vertex){//寻找该节点的祖先Vertex ancestorVertex=Find(ancestor.get(vertex));//如果祖先发生了变化,则更新记录新的祖先if(ancestorVertex!=ancestor.get(vertex))ancestor.put(vertex,ancestorVertex);}//返回其祖先return ancestor.get(vertex);}
}
 
测试函数
//测试函数
public class Main {/*并查集:简述:对集合进行分类合并,方便后续查找实现步骤:1)对所有顶点标号,其祖先节点默认为自己2)合并:以两个点中祖先标号小的作为新祖先进行合并3)查找:查找点的祖先,并更新查找路径点的祖先*/public static void main(String[] args) {//扫描器Scanner scanner=new Scanner(System.in);//存放顶点List<Vertex>vertexs=new LinkedList<>();//有直接关联的顶点List<List<Vertex>>connectVertexs=new LinkedList<>();System.out.println("请输入顶点的数量:");Integer vexcnt= scanner.nextInt();System.out.println("请输入这些顶点的编号");for(int i=0;i<vexcnt;i++){vertexs.add(new Vertex(scanner.nextInt()));}System.out.println("请输入有关系顶点的对数:");Integer connectVertexCnt= scanner.nextInt();System.out.println("请输入有关系顶点的编号:");for(int i=0;i<connectVertexCnt;i++){Integer id1= scanner.nextInt();Integer id2= scanner.nextInt();//获取这两个顶点Vertex v1=null;Vertex v2=null;for(int j=0;j<vertexs.size();j++){if(vertexs.get(j).id==id1)v1=vertexs.get(j);if(vertexs.get(j).id==id2)v2=vertexs.get(j);}LinkedList<Vertex>conVertexs=new LinkedList<>();conVertexs.add(v1);conVertexs.add(v2);connectVertexs.add(conVertexs);}//用并查集的操作类实现这些点的分类和查找UnionFindSetOperator ufs=new UnionFindSetOperator(vertexs,connectVertexs);//查找每一个点的祖先for(int i=0;i<vertexs.size();i++){Vertex ancestor=ufs.Find(vertexs.get(i));System.out.println("顶点:"+vertexs.get(i).id+"的祖先id为:"+ancestor.id);}}
}
自测

        测试模型:

        测试结果:

 

相关文章:

算法篇 : 并查集

介绍 英文名&#xff1a;union find set 作用&#xff1a;合并集合&#xff0c;查询集合 合并&#xff1a;将有直接关系的顶点放在一个集合里面 查找&#xff1a;查询某个顶点所属的集合 集合的标志&#xff1a;用祖先点的标号作为每个集合的标识 案例 如果说将下图的集合2合并…...

AM@微积分基本定理@微积分第二基本定理

文章目录 abstract微积分第二基本定理微积分基本公式公式书写例 结合不定积分的方法求定积分定积分换元法证明 定积分换元公式逆用例 和不定积分第二类换元法的差别定积分分部积分法例 abstract 微积分第一基本定理告诉我们,总是能够通过积分法构造(表达)一个连续函数的原函数…...

goland常用快捷键

移动光标 控制光标的移动&#xff1a;fn上下左右 移至当前页的页头&#xff1a;ctrlPgUp 移至并选中光标到当前页头&#xff1a;ctrlshiftPgUp 移至当前页的页尾&#xff1a;ctrlPgDn 移至并选中当前光标到当前页尾&#xff1a;ctrlshiftPgDn 返回到当前的光标处&#xf…...

CSDN写文章时常见问题及技巧

CSDN写文章时常见问题及技巧 1.有序待续、更新中 1.有序 过程&#xff1a; 写 1.空格 &#xff0c;注意“.”后加个空格就可以生成序号&#xff0c;随心所欲编辑了 待续、更新中 ————————————————————— 以上就是今日博客的全部内容了 创作不易,若对您有…...

JVM虚拟机详解

目录 01JVM由哪些部分组成/运行流程 什么是程序计数器 详细介绍堆 介绍方法区&#xff08;Method Area&#xff09; 直接内存 虚拟机栈(Java Virtual machine Stacks) 垃圾回收是否涉及栈内存 栈内存分配越大越好吗 方法内的局部变量是否线程安全 什么情况下会导致栈…...

Go 怎么操作 OSS 阿里云对象存储

1 介绍 在项目开发中&#xff0c;我们经常会使用对象存储&#xff0c;比如 Amazon 的 S3&#xff0c;腾讯云的 COS&#xff0c;阿里云的 OSS 等。本文我们以阿里云 OSS 为例&#xff0c;介绍怎么使用 Go 操作对象存储。 阿里云 OSS 提供了 REST Api 和 OSS Go SDK&#xff0…...

vue3 Suspense组件

在 Vue 3 中&#xff0c;<Suspense> 组件用于处理异步组件加载时的等待状态和错误处理。它允许你在加载异步组件时显示一个自定义的加载指示器&#xff0c;以及在加载失败时显示错误信息。以下是一个详细的 <Suspense> 组件的使用示例&#xff1a; 首先&#xff0…...

NlogPrismWPF

文章目录 Nlog&Prism&WPF日志模块实现原理添加配置注入服务应用测试其他模块怎么调用&#xff1f; Nlog&Prism&WPF 日志模块 介绍了为WPF框架Prism注册Nlog日志服务的方法 实现原理 无论是在WPF或者ASP.NET Core当中, 都可以使用ServiceCollection来做到着…...

文件上传漏洞(2), 文件上传实战绕过思路, 基础篇

文件上传漏洞实战思路(基础) 准备一句话木马文件 mm.php 一, 前端绕过 p1 浏览器禁用js先把mm.php后缀名修改为mm.jpg, 点击提交后, 用 burp 截取请求, 将数据包中的文件名修改回mm.php再提交. 二, 类型MIME绕过 p2 使用 burp 修改 Content-Type: image/jpeg 三, 黑名单绕…...

论文阅读 - Hidden messages: mapping nations’ media campaigns

论文链接&#xff1a; https://link.springer.com/content/pdf/10.1007/s10588-023-09382-7.pdf 目录 1 Introduction 2 The influence model 2.1 The influence‑model library 3 Data 4 Methodology 4.1 Constructing observations 4.2 Learning the state‑transiti…...

[AutoSAR系列] 1.3 AutoSar 架构

依AutoSAR及经验辛苦整理&#xff0c;原创保护&#xff0c;禁止转载。 专栏 《深入浅出AutoSAR》 1. 整体架构 ​ 图片来源&#xff1a; AutoSar 官网 从官往图中可以看出autosar作为汽车ECU软件架构&#xff0c;是通过分层来实现软硬件隔离。就像大多数操作系统一样&#xff…...

迁移学习 - 微调

什么是与训练和微调&#xff1f; 你需要搭建一个网络模型来完成一个特定的图像分类的任务。首先&#xff0c;你需要随机初始化参数&#xff0c;然后开始训练网络&#xff0c;不断调整参数&#xff0c;直到网络的损失越来越小。在训练的过程中&#xff0c;一开始初始化的参数会…...

09 用户态跟踪:如何使用eBPF排查应用程序?

09 用户态跟踪&#xff1a;如何使用eBPF排查应用程序&#xff1f; sudo bpftrace -e usdt:/usr/bin/python3:function__entry { printf("%s:%d %s\n", str(arg0), arg2, str(arg1))} # -*- coding: UTF-8 -*- import socket from socket import SOL_SOCKET, SO_R…...

深入浅出排序算法之堆排序

目录 1. 算法介绍 2. 执行流程⭐⭐⭐⭐⭐✔ 3. 代码实现 4. 性能分析 1. 算法介绍 堆是一种数据结构&#xff0c;可以把堆看成一棵完全二叉树&#xff0c;这棵完全二叉树满足&#xff1a;任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小&#x…...

Linux 命令(11)—— tcpdump

文章目录 一、命令简介二、使用方法三、命令选项四、基本语法和使用方法1. 显示 ASCII 字符串2. 抓取特定协议的数据3. 抓取特定主机的数据4. 将抓取的数据写入文件5. 行缓冲模式 五、理解tcpdump的输出六、过滤表达式1. Host 过滤2. Network 过滤3. Proto 过滤4. Port 过滤5. …...

8.自定义组件布局和详解Context上下文

pages/index.vue layout布局运行在服务端 1、在项目的目录下新建layout文件夹&#xff0c;并新建一个blog.vue布局文件 2、在页面中的layout函数里&#xff0c;返回刚才新建布局文件的名字blog就可以使用了 export default {...layout (context) {console.log(context)retu…...

几个Web自动化测试框架的比较:Cypress、Selenium和Playwright

介绍&#xff1a;Web自动化测试框架对于确保Web应用程序的质量和可靠性至关重要。它们帮助开发人员和测试人员自动执行重复性任务&#xff0c;跨多个浏览器和平台执行测试&#xff0c;并在开发早期发现问题。 以下仅代表作者观点&#xff1a; 本文探讨来3种流行的Web自动化测…...

Android Studio中配置aliyun maven库

当下载第三方库失败的时候&#xff0c;通过Android Studio中配置aliyun maven库&#xff0c;达到正常下载库效果 在项目的根build.gradle里面&#xff08;不是module&#xff09;buildscriptde对应位置添加配置&#xff1a; maven { url https://maven.aliyun.com/repository/…...

记录使用阿里 ARoute 遇到的坑

1.按照官方一个配置好之后 尝试使用 跳转出现 Aroute Theres no route matched path"" 我这边遇到的坑是配置问题 kotiln 使用了 Java的配置 plugins {id("com.android.application")id("org.jetbrains.kotlin.android")id("kotlin-kapt&…...

lesson2(补充)关于const成员函数

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 前言&#xff1a; 将const 修饰的 “ 成员函数 ” 称之为 const 成员函数 &#xff0c; const 修饰类成员函数&#xff0c;实际修饰该成员函数 隐含的 this 指针 &#xff0c;表明在该成员函数中不能对类的任何成员进行修改…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

动态规划-1035.不相交的线-力扣(LeetCode)

一、题目解析 光看题目要求和例图&#xff0c;感觉这题好麻烦&#xff0c;直线不能相交啊&#xff0c;每个数字只属于一条连线啊等等&#xff0c;但我们结合题目所给的信息和例图的内容&#xff0c;这不就是最长公共子序列吗&#xff1f;&#xff0c;我们把最长公共子序列连线起…...