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

并查集(未压缩未按秩合并)

并查集(Union-Find)是一种用于处理不相交集合(disjoint-set)的数据结构,主要用于处理连通性问题。并查集支持两种操作:

  1. 查找(Find):确定元素所属的集合。
  2. 合并(Union):将两个集合合并为一个集合。

并查集通常应用于图的连通性问题,例如判断图中两点是否连通、计算连通分量等。

动画描述

将(1,2),(2,3),(2,4)union后的图例,可以观察到不带压缩的情况下树的高度在持续增长。

问题描述

下面是一个不带路径压缩的并查集(Union-Find)。这个版本仅使用基本的查找和合并操作:

代码实现

public class SimpleUnionFind {private int[] parent;// 初始化并查集public SimpleUnionFind(int size) {parent = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;}}// 查找操作,不带路径压缩public int find(int p) {while (p != parent[p]) {p = parent[p];}return p;}// 合并操作,不带按秩合并public void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP != rootQ) {parent[rootP] = rootQ;}}// 判断两个节点是否连通public boolean connected(int p, int q) {return find(p) == find(q);}public static void main(String[] args) {int size = 10; // 假设有10个元素SimpleUnionFind uf = new SimpleUnionFind(size);uf.union(1, 2);uf.union(2, 3);uf.union(4, 5);uf.union(6, 7);uf.union(5, 6);System.out.println("1 和 3 是否连通: " + uf.connected(1, 3)); // trueSystem.out.println("1 和 4 是否连通: " + uf.connected(1, 4)); // falseSystem.out.println("4 和 7 是否连通: " + uf.connected(4, 7)); // trueuf.union(1, 4);System.out.println("1 和 4 是否连通: " + uf.connected(1, 4)); // true}
}

解释

  1. 初始化:

    • parent数组用于存储每个元素的父节点,初始时每个元素的父节点是它自己。
  2. 查找操作(find):

    • 查找元素所属的集合,通过不断访问父节点来找到根节点。因为没有路径压缩,树的高度可能会很高,查找的时间复杂度是O(n)(n是元素个数)。
  3. 合并操作(union):

    • 合并两个集合,将一个集合的根节点指向另一个集合的根节点。因为没有按秩合并,树的高度可能会很高,合并的时间复杂度也是O(n)。
  4. 连通性检查(connected):

    • 判断两个元素是否属于同一个集合,即查找它们的根节点是否相同。

这个实现是并查集的基础版本,没有进行路径压缩和按秩合并的优化,因此在处理较大的数据集时效率较低。路径压缩和按秩合并的优化可以显著提高并查集的性能。

相关文章:

并查集(未压缩未按秩合并)

并查集&#xff08;Union-Find&#xff09;是一种用于处理不相交集合&#xff08;disjoint-set&#xff09;的数据结构&#xff0c;主要用于处理连通性问题。并查集支持两种操作&#xff1a; 查找&#xff08;Find&#xff09;&#xff1a;确定元素所属的集合。合并&#xff0…...

读书其实并没有那么大的作用

开场白 Hey&#xff0c;书虫们和生活探索者们&#xff01;今天我们来聊聊一个老生常谈却又常谈常新的话题——读书。有人说&#xff0c;读书能改变命运&#xff0c;但也有人说&#xff0c;读书不过是生活的调味品。那么&#xff0c;读书到底有啥用&#xff1f;让我们一起来扒一…...

微信小程序/vue将金额/数字转为千分位显示在页面上

vue将金额转为数字显示在页面上 toThousands (number) {let isNegative_ false // 判断正负if (Number(number) < 0) {isNegative_ truenumber String(number).split(-)[1] // 分离负号 并把String类型的数字并赋值给number}if (Number(number) ! 0 && Math.abs…...

如何查看树莓派的 OS 和内核版本

在使用树莓派开发的时候&#xff0c;有时候需要知道树莓派的一些基本信息&#xff0c;如&#xff1a;OS 版本&#xff0c;内核版本&#xff0c;CPU 构架等&#xff0c;在使用 40 pin 扩展接口的时候&#xff0c;需要知道每个管脚的具体定义。 1. 查看‌ OS 版本&#xff1a; 使…...

php的mysql操作可实现简单登录功能

文章目录 1. 表单和请求(1) 表单操作(2) 网络请求(3) $_REQUEST超全局变量 2. mysql数据库操作1) mysqli连接操作2) 操作数据库3) 预处理语句4) pdo操作数据库5) 创建连接并执行查询语句 1. 表单和请求 主要使用到**$_GET** 和 $_POST这两个超全局变量,分别对应两种请求 (1) …...

c#复制窗体Form方法

直接复制三个类粘贴到vs的项目中...

C:图案打印

引言 本篇文章讲了一些常见的图形编程题&#xff0c;并总结了一些规律。 1、打印空心正方形 1.1 代码展示&#xff1a; #include<stdio.h> int main() {int a 0;//边长初始化scanf("%d", &a);//输入边长的值{int i 0;for (i 0; i < a; i)//控制行…...

WebLogic:弱口令,木马反弹连接

weblogic WebLogic 是 Oracle 公司开发的应用服务器&#xff0c;主要用作开发、集成、部署和管理大型分布式 Web 应用、网络应用和数据库应用的 Java 应用服务器。它在历史上曾出现过多个安全漏洞&#xff0c;其中包括弱口令、任意文件上传、SSRF、反序列化漏洞等 常见版本&a…...

深度学习图像处理环境搭建

Anaconda安装 Anaconda介绍 Anaconda是一个用于科学计算和数据科学的开源发行版&#xff0c;它包含了许多流行的Python库和工具&#xff0c;旨在简化数据分析和机器学习任务的开发过程。Anaconda提供了一个集成的开发环境&#xff0c;包括Python解释器、包管理工具&#xff0…...

这几个高级爬虫软件和插件真的强!

亮数据&#xff08;Bright Data&#xff09; 亮数据是一款强大的数据采集工具&#xff0c;以其全球代理IP网络和强大数据采集技术而闻名。它能够轻松采集各种网页数据&#xff0c;包括产品信息、价格、评论和社交媒体数据等。 网站&#xff1a;https://get.brightdata.com/we…...

【实战】机器学习Kaggle比赛—House Prices - Advanced Regression Techniques

House Prices - Advanced Regression Techniques 一、准备工作&#xff08;1&#xff09;查看项目概述&#xff08;2&#xff09;下载数据集&#xff08;3&#xff09;导入部分必要的库&#xff08;4&#xff09;参数设置&#xff08;图形显示大小屏蔽警告&#xff09;&#xf…...

【前端面试题】前端工程化、Webpack、Vite、Git项目管理相关问题

目录 关于前端工程化关于Webpack关于Vite关于Git项目管理综合性问题 关于前端工程化 1. 前端工程化的定义和好处 问题&#xff1a;什么是前端工程化&#xff1f;它的主要好处是什么&#xff1f;答案&#xff1a;前端工程化是指在前端开发中应用系统化、自动化和标准化的方法&…...

【号外】「省点时间」新功能暖心上线!

好消息&#xff0c;好消息&#xff0c;重大好消息&#xff01; 应广大用户朋友的要求&#xff0c;经过一个多月的鏖战&#xff0c;「省点时间」的VIP功能终于上线啦&#xff01; 新版本在原有基础上&#xff0c;新增VIP功能&#xff0c;用户拥有了更多选择&#xff0c;赶快来…...

Python面试题:如何使用WebSocket实现实时Web应用

使用 WebSocket 实现实时 Web 应用可以使你的应用程序具备实时双向通信的能力。以下是一个完整的指南&#xff0c;展示如何使用 Django Channels 和 WebSocket 实现一个简单的实时 Web 应用。 环境准备 安装 Django Channels: pip install channels创建 Django 项目: django-a…...

公交信息在线查询小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;线路信息管理&#xff0c;站点分类管理&#xff0c;站点信息管理&#xff0c;周边分类管理周边信息管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0…...

Airtest实施手机精准截图

Airtest实施手机精准截图 一、接口查找 首先我们需要知道我们应该怎么实现用脚本去进行局部截图&#xff0c;我们可以通过翻阅Airtest的API文档发现&#xff0c;Airtest提供了 crop_image(img, rect) 方法可以帮助我们实现局部截图&#xff0c;在我们往期的推文里也介绍过该接…...

前端面试宝典【设计模式】【2】

欢迎来到《前端面试宝典》,这里是你通往互联网大厂的专属通道,专为渴望在前端领域大放异彩的你量身定制。通过本专栏的学习,无论是一线大厂还是初创企业的面试,都能自信满满地展现你的实力。 核心特色: 独家实战案例:每一期专栏都将深入剖析真实的前端面试案例,从基础知…...

技术汇总笔记7:条件分支相关内容

嵌套Switch语句的使用和改进 嵌套的switch语句虽然在语法上是允许的&#xff0c;但可能会使代码难以阅读和维护。例如&#xff1a; switch (_get_urgency_ob_type(sData.structure_name)) {case URGENCY_OB_PRESSUREINFO:{switch(_get_urgency_ob_sub_type( sData.attribute_…...

一文让你学会python:面向对象

面向对象编程&#xff08;OOP&#xff09; 一.类与实例 1.类&#xff1a; 是对现实世界描述的一种类型&#xff0c;是抽象的&#xff0c;是实例的模板&#xff0c;类名采用大驼峰&#xff0c;定义方式为 class 类名: pass 。 2.实例&#xff1a; 根据类创建的具体对象&…...

mac电脑安装 docker镜像 btpanel/baota

PS&#xff1a;docker链接&#xff1a;https://hub.docker.com/r/btpanel/baota 1、将docker下载到本地&#xff0c;然后运行端口映射 docker run -d --restart unless-stopped --name baota -p 8888:8888 -p 22:22 -p 443:443 -p 80:80 -p 888:888 -v ~/website_data:/www/w…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

python如何将word的doc另存为docx

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

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...