基于C#实现并查集
一、场景
有时候我们会遇到这样的场景,比如:M={1,4,6,8},N={2,4,5,7},我的需求就是判断{1,2}是否属于同一个集合,当然实现方法有很多,一般情况下,普通青年会做出 O(MN)的复杂度,那么有没有更轻量级的复杂度呢?并查集就是用来解决这个问题的。
二、操作
从名字可以出来,并查集其实只有两种操作,并(Union)和查(Find),并查集是一种算法,所以我们要给它选择一个好的数据结构,通常我们用树来作为它的底层实现。
2.1、节点定义
#region 树节点/// <summary>/// 树节点/// </summary>public class Node{/// <summary>/// 父节点/// </summary>public char parent;/// <summary>/// 节点的秩/// </summary>public int rank;}#endregion
2.2、Union 操作
<1> 原始方案
首先我们会对集合的所有元素进行打散,最后每个元素都是一个独根的树,然后我们 Union 其中某两个元素,让他们成为一个集合,最坏情况下我们进行 M 次的 Union 时会存在这样的一个链表的场景。

从图中我们可以看到,Union 时出现了最坏的情况,而且这种情况还是比较容易出现的,最终导致在 Find 的时候就相当复杂了,为 O(N)。
<2> 按秩合并
我们发现出现这种情况的原因在于我们 Union 时都是将合并后的大树作为小树的孩子节点存在,那么我们在 Union 时能不能判断一下,将小树作为大树的孩子节点存在,最终也就降低了新树的深度,比如图中的 Union(D,{E,F})的时候可以做出如下修改。

可以看出,我们有效的降低了树的深度,在 N 个元素的集合中,构建树的深度不会超过 LogN 层。M 次操作的复杂度为 O(MlogN),从代码上来说,我们用 Rank 来统计树的秩,可以理解为树的高度,独根树时 Rank=0,当两棵树的 Rank 相同时,可以随意挑选合并,在新根中的 Rank++ 就可以了。
#region 合并两个不相交集合/// <summary>/// 合并两个不相交集合/// </summary>/// <param name="root1"></param>/// <param name="root2"></param>/// <returns></returns>public void Union(char root1, char root2){char x1 = Find(root1);char y1 = Find(root2);//如果根节点相同则说明是同一个集合if (x1 == y1)return;//说明左集合的深度 < 右集合if (dic[x1].rank < dic[y1].rank){//将左集合指向右集合dic[x1].parent = y1;}else{//如果 秩 相等,则将 y1 并入到 x1 中,并将x1++if (dic[x1].rank == dic[y1].rank)dic[x1].rank++;dic[y1].parent = x1;}}#endregion
2.3、Find 操作
我们学算法,都希望能把一个问题优化到不能优化的地步,针对 logN 的级别,我们还能优化吗?当然可以。
<1> 路径压缩
在 Union 和 Find 这两种操作中,显然我们在 Union 上面已经做到了极致,下面我们在 Find 上面考虑一下,是不是可以在 Find 上运用伸展树的思想,这种伸展思想就是压缩路径。

从图中我们可以看出,当我 Find(F)的时候,找到“F”后,我们开始一直回溯,在回溯的过程中给,把该节点的父亲指向根节点。最终我们会形成一个压缩后的树,当我们再次 Find(F)的时候,只要 O(1)的时间就可以获取,这里有个注意的地方就是 Rank,当我们在路径压缩时,最后树的高度可能会降低,可能你会意识到原先的 Rank 就需要修改了,所以我要说的就是,当路径压缩时,Rank 保存的就是树高度的上界,而不仅仅是明确的树高度,可以理解成"伸缩椅"伸时候的长度。
#region 查找x所属的集合/// <summary>/// 查找x所属的集合/// </summary>/// <param name="x"></param>/// <returns></returns>public char Find(char x){//如果相等,则说明已经到根节点了,返回根节点元素if (dic[x].parent == x)return x;//路径压缩(回溯的时候赋值,最终的值就是上面返回的"x",也就是一条路径上全部被修改了)return dic[x].parent = Find(dic[x].parent);}#endregion
我们注意到,在路径压缩后,我们将 LogN 的复杂度降低到 Alpha(N),Alpha(N)可以理解成一个比 hash 函数还有小的常量,这就是算法的魅力。

相关文章:
基于C#实现并查集
一、场景 有时候我们会遇到这样的场景,比如:M{1,4,6,8},N{2,4,5,7},我的需求就是判断{1,2}是否属于同一个集合,当然实现方法有很多,一般情况下,普通青年会做出 O(MN)的复杂度,那么有没有更轻量级的复杂度呢…...
opencv-图像轮廓
轮廓可以简单认为成将连续的点(连着边界)连在一起的曲线,具有相同的颜色或者灰度。轮廓在形状分析和物体的检测和识别中很有用。 • 为了更加准确,要使用二值化图像。在寻找轮廓之前,要进行阈值化处理或者 Canny 边界检…...
小黑子—Maven高级
Maven高级篇 二 小黑子的Maven高级篇学习1. 分模块开发1.1 分模块开发设计1.2 分模块开发实现1.2.1 抽取domain层1.2.2 抽取dao层 2. 依赖管理2.1 依赖传递2.2 可选依赖2.3 排除依赖 3. 继承与聚合3.1 聚合3.2 继承3.3 总结 4. 属性4.1 配置文件加载属性4.2 版本管理 5. 多环境…...
一个正整数转为2进制和8进制,1的个数相同的第23个数是什么?
package cn.com;import java.lang.*;//默认加载public class C2 {//10进制转8进制static int HtoO(int n){int cnt 0;while(n!0){cntn%8;n/8;}return cnt;}//10进制转2进制static int HtoB(int n){int cnt 0;while(n!0){cntn%2;n/2;}return cnt;}public static void main(Str…...
Unity阻止射线穿透UI的方法之一
if(UnityEngine.EventSystems.EventSystem.current.IsPointerOverGameObject()) return; 作者:StormerZ https://www.bilibili.com/read/cv27797873/ 出处:bilibili...
HarmonyOS开发:ArkTs常见数据类型
前言 无论是Android还是iOS开发,都提供了多种数据类型用于常见的业务开发,但在ArkTs中,数据类型就大有不同,比如int,float,double,long统一就是number类型,当然了也不存在char类型&…...
Unsupervised MVS论文笔记
Unsupervised MVS论文笔记 摘要1 引言2 相关工作3 实现方法3.1 网络架构3.2 通过光度一致性学习3.3 MVS的鲁棒光度一致性3.4 学习设置和实施的细节3.5.预测每幅图像的深度图 4 实验4.1 在DTU上的结果4.2 消融实验 Tejas Khot and Shubham Agrawal and Shubham Tulsiani and Chr…...
Matplotlib图形注释_Python数据分析与可视化
Matplotlib图形注释 添加注释文字、坐标变换 有的时候单单使用图形无法完整清晰的表达我们的信息,我们还需要进行文字进行注释,所以matplotlib提供了文字、箭头等注释可以突出图形中重点信息。 添加注释 为了使我们的可视化图形让人更加容易理解&#…...
如何把A3 pdf 文章打印成A4
1. 用Adobe Acrobat 打开pdf 2 打印 选择海报 进行调整即可如下图,见下面红色的部分。...
【Vue】vue指令
目录 V-html v-show和v-if v-show 显示 隐藏 v-if 显示 隐藏 总结 显示隐藏的应用场景 未登录的情况 登录的情况 v- else 和 v-else-if v-if 和v-else v-if 和 v-else-if 总结: v-on 语法一: 语法二: 调用传参 v-bind…...
记录华为云服务器(Linux 可视化 宝塔面板)-- 安全组篇
文章目录 前言安全组说明安全组的特性安全组的应用场景 进入安全组添加基本规则添加自定义规则如有启发,可点赞收藏哟~ 前言 和windows防火墙类似,安全组是一种虚拟防火墙,具备状态检测和数据包过滤功能,可以对进出云服务器的流量…...
基于Python 中创建 Sentinel-2 RGB 合成图像
一、前言 下面的python代码将带您了解如何从原始 Sentinel-2 图像创建 RGB 合成图像的过程。 免费注册后,可以从 Open Access Hub 下载原始图像。 请注意,激活您的帐户可能需要 24 小时! 二、准备工作 (1)导入必要的库…...
保姆级连接FusionInsight MRS kerberos Hive
数新网络,让每个人享受数据的价值https://xie.infoq.cn/link?targethttps%3A%2F%2Fwww.datacyber.com%2F 概述 本文将介绍在华为云 FusionInsight MRS(Managed Relational Service)的Kerberos环境中,如何使用Java和DBeaver实现远…...
electerm 跨平台的终端 /ssh/sftp 客户端
文章目录 electerm功能特性主题配色 electerm 每个程序员基本都离开SSH链接工具,目前市场上好用的基本都是收费的 给大家推荐一款国人开发的开源链接工具https://github.com/electerm/electerm 到目前为止star已经9.5K了,非常受欢迎 功能特性 支持ssh,telnet,serialport,本地和…...
Anthropic LLM论文阅读笔记
研究时间:与Instrcut GPT同期的工作,虽然其比ChatGPT发布更晚,但是其实完成的时间比ChatGPT更早。与ChatGPT的应用区别:该模型比ChatGPT回答我不知道的概率更高。将强化学习用于大语言模型(RLHF)࿱…...
docker启动容器失败,然后查看日志,docker logs查看容器出现报错:
docker 启动容器失败,然后docker logs 查看容器出现报错: error from daemon in stream: Error grabbing logs: invalid character l after object key:value pair在网上看到的 解决方案: 找到你日志文件目录: docker inspect …...
【开源】基于Vue.js的网上药店系统
项目编号: S 062 ,文末获取源码。 \color{red}{项目编号:S062,文末获取源码。} 项目编号:S062,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 药品类型模块2.3 药…...
App 设计工具
目录 说明 打开 App 设计工具 示例 创建 App 创建自定义 UI 组件 打开现有 App 文件 打包和共享 App 本文主要讲述以交互方式创建 App。 说明 App 设计工具是一个交互式开发环境,用于设计 App 布局并对其行为进行编程。 可以使用 App 设计工具:…...
毅速:3D打印随形透气钢为解决模具困气提供了新助力
在模具行业中,困气是一个较常见的问题。解决困气问题的方法有很多,透气钢就是其一。传统的制造的透气钢往往存在一些不足,如加工难度大、无法满足复杂形状的需求等。随着3D打印技术的发展,一种新型的随形透气钢技术逐渐崭露头角&a…...
某软件商店app抓包分析与sign加密算法实现
文章目录 1. 写在前面2. 抓包配置3. 抓包分析4. 接口测试5. sign加密算法6. 数据效果展示 【作者主页】:吴秋霖 【作者介绍】:Python领域优质创作者、阿里云博客专家、华为云享专家。长期致力于Python与爬虫领域研究与开发工作! 【作者推荐】…...
STM32F4 GPIO寄存器直击:告别库函数,手把手带你用C代码点亮LED(附5V容忍引脚查询方法)
STM32F4 GPIO寄存器直击:告别库函数,手把手带你用C代码点亮LED(附5V容忍引脚查询方法) 在嵌入式开发领域,真正掌握硬件本质的开发者往往能写出更高效、更可靠的代码。对于STM32系列微控制器而言,理解GPIO寄…...
从ELF文件头到机器码:手把手带你用objdump解剖Linux可执行文件
从ELF文件头到机器码:手把手带你用objdump解剖Linux可执行文件 在计算机的世界里,每个可执行程序都像一本精心编写的书,而ELF(Executable and Linkable Format)就是这本书的标准格式。当我们编译一个简单的"Hello…...
植物大战僵尸终极修改器:PVZ Toolkit完整使用教程
植物大战僵尸终极修改器:PVZ Toolkit完整使用教程 【免费下载链接】pvztoolkit 植物大战僵尸 PC 版综合修改器 项目地址: https://gitcode.com/gh_mirrors/pv/pvztoolkit 植物大战僵尸PVZ Toolkit是一款专为经典塔防游戏《植物大战僵尸》PC版设计的综合辅助工…...
假期机器学习实战书单:从入门到精通的指南
1. 假期机器学习书单:从入门到精通的实战指南又到了年末假期季,对于技术人来说,这段时间最适合静下心来系统学习新技能。作为从业多年的机器学习工程师,我每年都会收到大量关于"如何选择机器学习书籍"的咨询。不同于市面…...
从4邻接、8邻接到m邻接:像素关系与距离度量全解析
1. 像素邻接性的基础概念 当你第一次接触数字图像处理时,可能会被各种"邻接"概念搞得晕头转向。别担心,这就像认识新邻居一样简单。想象一下,你住在一个小区里,4邻接就是你前后左右的四户人家,8邻接则是再加…...
yfinance终极指南:轻松获取雅虎财经数据的Python利器
yfinance终极指南:轻松获取雅虎财经数据的Python利器 【免费下载链接】yfinance Download market data from Yahoo! Finances API 项目地址: https://gitcode.com/GitHub_Trending/yf/yfinance 在量化投资和金融数据分析领域,获取准确、及时的金融…...
Java项目如何72小时内完成Loom响应式升级?一线大厂已验证的5个避坑清单
第一章:Loom响应式升级的必要性与72小时落地可行性论证现代Java应用在高并发、低延迟场景下面临线程模型瓶颈,传统Thread-per-Request模式导致资源开销剧增、GC压力攀升、上下文切换成本不可忽视。Project Loom引入虚拟线程(Virtual Threads&…...
从dbus-send到busctl:手把手教你迁移到更现代的D-Bus调试工具链
从dbus-send到busctl:现代D-Bus调试工具链迁移实战指南 如果你曾经在Linux系统中与D-Bus打交道,那么对dbus-send这个老牌命令行工具一定不陌生。它就像一把瑞士军刀,虽然功能全面但用起来总有些笨拙——复杂的参数构造、晦涩的输出格式、缺乏…...
Steam创意工坊下载实践指南:WorkshopDL深度解析
Steam创意工坊下载实践指南:WorkshopDL深度解析 【免费下载链接】WorkshopDL WorkshopDL - The Best Steam Workshop Downloader 项目地址: https://gitcode.com/gh_mirrors/wo/WorkshopDL 你是否在GOG或Epic Games Store购买了游戏,却无法访问St…...
用旧投影仪和普通摄像头DIY结构光扫描仪:3D Scanning Software实战建模全记录
用旧投影仪和普通摄像头DIY结构光扫描仪:3D Scanning Software实战建模全记录 当创客精神遇上三维重建技术,一台闲置的投影仪加上普通USB摄像头就能变身专业级扫描设备。这种低成本结构光方案在开源软件加持下,精度足以满足手办复制、零件逆向…...
