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

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

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

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

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...