【数据结构-图论】并查集
并查集(Union-Find)是一种数据结构,它提供了处理一些不交集的合并及查询问题的高效方法。并查集主要支持两种操作:
查找(Find):确定某个元素属于哪个子集,这通常意味着找到该子集的“代表元素”或“根元素”。
合并(Union):将两个子集合并成一个集合。
并查集通过数组或树形结构来实现,其中每个节点指向其父节点,根节点指向自身,这样形成一个或多个树形结构。每棵树代表一个集合,树根的标识符(通常是数组的索引)代表整个集合的标识符。
基本概念:
初始化:开始时,每个元素各自构成一个单元素集合,即每个元素的父节点是其自身。
路径压缩:在执行查找操作时,将查找路径上的每个节点直接连接到根节点,这样可以加快后续查找的速度。
按秩合并:合并时,总是将更小的树连接到更大的树的根节点上,这可以帮助避免树变得过深,从而保持操作的效率。
并查集的重要思想在于,用集合中的一个元素代表集合。

现在1号和3号比武,假设1号赢了(这里具体谁赢暂时不重要),那么3号就认1号作帮主(合并1号和3号所在的集合,1号为代表元素)。

现在2号想和3号比武(合并3号和2号所在的集合),但3号表示,别跟我打,让我帮主来收拾你(合并代表元素)。不妨设这次又是1号赢了,那么2号也认1号做帮主。

上面大概介绍完了整体的东西下面介绍一下细节:

下面是代码部分:
// 查找i的代表元素,并进行路径压缩优化
int find(int i) {if (fa[i] == i) // 如果元素i指向自己,那么它是代表元素return i;elsereturn fa[i] = find(fa[i]); // 否则递归查找,并更新i的父链接为代表元素
}// 合并i和j所在的集合
void unionn(int i, int j) {int i_fa = find(i); // 查找i的代表元素int j_fa = find(j); // 查找j的代表元素fa[i_fa] = j_fa; // 将i的集合合并到j的集合中
}
find 函数通过递归查找找到一个元素的代表元素,并在查找的过程中将元素直接链接到代表元素,这个优化叫做路径压缩,它可以减少后续查找的时间。
unionn 函数将两个元素所在的集合合并成一个集合。它首先找到每个元素的代表元素,然后将其中一个集合的代表元素链接到另一个集合的代表元素上,从而完成合并。这里没有实现按秩合并或路径压缩的更复杂的优化。
下面是一道题

public class UnionFind {private int[] parent;public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}public int find(int x) {if (x != parent[x]) {parent[x] = find(parent[x]);}return parent[x];}public void union(int x, int y) {parent[find(x)] = find(y);}public boolean isConnected(int x, int y) {return find(x) == find(y);}public static void main(String[] args) {UnionFind uf = new UnionFind(10);uf.union(0, 1); // Marry person 1 and 2uf.union(2, 3); // Marry person 3 and 4boolean areMarried = uf.isConnected(1, 4); // Check if person 2 and 5 are relatedSystem.out.println(areMarried ? "YES" : "NO"); // Output should be "NO" if unrelated}
}
相关文章:
【数据结构-图论】并查集
并查集(Union-Find)是一种数据结构,它提供了处理一些不交集的合并及查询问题的高效方法。并查集主要支持两种操作: 查找(Find):确定某个元素属于哪个子集,这通常意味着找到该子集的…...
云计算时代的运维: 职业发展方向与岗位选择
✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua,在这里我会分享我的知识和经验。&#x…...
java锁底层概述
Java中的锁是并发编程中核心的同步机制之一,用于控制多个线程对共享资源的访问,以保证数据的一致性和完整性。Java锁的底层实现依赖于操作系统的原生线程模型和Java虚拟机(JVM)的实现。这里主要讨论两种常见的锁:synch…...
win10如何添加指纹登陆
1、首先进入设置,进入下一个设置页面 2、在下一个设置页面内,我们直接使用右上角的搜索框,输入“指纹/finger”进行搜索。回车之后进入设置指纹登陆选项 3、设置指纹登陆的前期是设置好你的密码和pin码(先要设定登录密码和pin码),这里pin和密码都可以直接登陆我们的win10,设…...
足底筋膜炎的症状及治疗
足底筋膜炎症状:足底筋膜炎通常表现为足跟部疼痛,尤其是在晨起或长时间站立、行走后加重。疼痛可能向足底前部或足弓处放射,严重时可能影响行走。此外,患者还可能出现足跟部肿胀、皮肤温度升高、局部压痛等症状。 足底筋膜炎治疗方…...
udp丢包问题研究
//发现udp 有收不到数据包现象. 一: 观察丢包 1. ifconfig enp8s0 2. netstat -s -u 二: 修改系统缓存参数. recv_buffer_size 修改系统buffer_size sysctl -w net.core.rmem_max26214400 sysctl -w net.core.rmem_default26214400 三: 应用程序考虑 av_dict_set(&m_o…...
在idea中用模板骨架初始创建maven管理的web项目时没有src有关的目录的解决方案
一.问题如下 二.解决方法 首先关闭当前项目,接着修改全局设置,重新创建项目 在VM Options中添加"-DarchetypeCataloginternal",点击ok保存 点击创建,如果创建成功没报错且有src,就ok了。 当然如果出现以下…...
WPF 【十月的寒流】学习笔记(2):MVVM中是怎么实现通知的
文章目录 前言相关链接代码仓库项目配置代码初始代码ViewPersonViewModel 尝试老办法通知解决方案ObservableCollectionBindingListICollectionView 总结 前言 我们这次详细了解一下列表通知的底层是怎么实现的 相关链接 十月的寒流 MVVM实战技巧之:可被观测的集合…...
数据结构:广义表
定义:有序数列 表示GL=(a(b,c))长度 2, 表头:a 表尾:(&am…...
你好,C++(18) 到底要不要买这个西瓜?4.1.6 操作符之间的优先顺序
你好,C(18) 到底要不要买这个西瓜?4.1.6 操作符之间的优先顺序 4.1.6 操作符之间的优先顺序 在表达一些比较复杂的条件判断时,在同一个表达式中,有时可能会存在多个操作符。比如,我们在判断要…...
C语言 for 循环语句的基本格式是什么?
一、问题 for 循环语句在C语⾔中是最为常见的循环语句,其功能强⼤,⽽且⽤法灵活,那么它的基本格式是什么呢? 二、解答 for 语句的⼀般形式为: for(表达式1;表达式2;表达3)语句; 每条 for 语句包含三个⽤分…...
项目-SERVER模块-日志宏
日志宏 #define INF 0 #define DBG 1 #define ERR 2#define LOG_LEVEL INF #define LOG(level, format, ...) do {\if (level < LOG_LEVEL) break;\time_t t time(NULL);\struct tm *ltm localtime(&t);\char tmp[32] {0};\strftime(tmp, 31, "%H:%M:%S"…...
TCP为什么要三次握手?
TCP三次握手协议是为了在不可靠的互联网环境中可靠地建立起一个连接,三次握手可以确保两端的发送和接收能力都是正常的。 那么,为什么是三次而不是二次或四次握手呢? 为什么不是二次握手? 如果是二次握手,即客户端发…...
网络防御第6次作业
防病毒网关 按照传播方式分类 病毒 病毒是一种基于硬件和操作系统的程序,具有感染和破坏能力,这与病毒程序的结构有关。病毒攻击的宿主程序是病毒的栖身地,它是病毒传播的目的地,又是下一次感染的出发点。计算机病毒感染的一般过…...
Jmeter分布式部署
前期准备: 1. 控制机一台,代理机一台,Jmeter安装包 操作步骤: 1. Linux安装Jmeter(windows安装教程自己搜一下) 1.1创建一个单独的文件夹(jmeter),用来存放Jmeter的安装包 mkdir jmeter 1.2…...
Odoo迈入开源第一低代码开发平台的重要里程碑
Odoo17的正式发布已经过去好几个月了,通过一段时间的运用,最大的感触就是,Odoo会成为企业管理软件低代码开发平台的重要一员,而V17则会成为这个过程中具有里程碑意义的版本。 时隔四个月,让我们回头来看看Odoo17带来的…...
WinForm、Wpf自动升级 AutoUpdater.NET
Github AutoUpdater.NET 目录 一、IIS部署 更新站点 二、创建Winform 一、IIS部署 更新站点 IIS默认站点目录下创建 目录 Downloads、Updates Updates目录创建文件 UpdateLog.html、AutoUpdaterStarter.xml UpdateLog.html: <html><body><h1…...
GPU不够用:语言模型的分布式挑战
引言 随着深度学习技术的飞速发展,大规模语言模型(LLM)在各种NLP任务中取得了令人瞩目的成绩。然而,这些模型的大小和复杂度也不断增加,给部署和应用带来了诸多挑战。特别是在单个GPU或服务器的内存容量有限的情况下,如何高效地利用分布式计算资源成为了一个亟待解决的问…...
深入理解Redis中的渐进式Rehash技术
1. 引言 Redis是一款高性能的键值存储系统,被广泛应用于缓存、队列、计数器等场景,因其快速、稳定的特性备受开发者青睐。在Redis的背后,有着许多复杂的数据结构和算法支撑着其高效运行,而其中之一就是Rehash操作。 Rehash是Redis中的一个关键操作,负责在数据量增加时对…...
数据结构 栈和队列 力扣例题AC——代码以及思路记录
20. 有效的括号 给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...
