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

数据结构详细笔记——并查集

文章目录

  • 逻辑结构
  • 存储结构
  • 并、查代码实现
    • Union 操作的优化
    • Find 操作的优化(压缩路径)


逻辑结构

集合:将各个元素划分为若干个互不相交的子集的集合
森林是m(m>=0)棵互不相交的树的集合

存储结构

#define SIZE 13
int UFSets[SIZE];    // 集合元素数组// 初始化并查集
void Initial(int S[]){for(int i=0;i<SIZE;i++)S[i] = -1;
}

并、查代码实现

// Find 查操作,找x所属集合(返回x所属的根结点) 时间复杂度O(n)
int Find(int S[],int x){while(S[x]>0)  // 循环寻找x的根x=S[x];return x;      // 根的S【】小于0
}// Union 并操作,将两个集合合并为一个  时间复杂度O(n)
void Union(int S[],int Root1,int Root2){// 要求Root1与Root2是不同的集合if(Root1==Root2) return// 将根Root2连接到另一根Root1下面S[Root2]=Root1;

Union 操作的优化

优化思路:在每次Union操作构建树的时候,尽可能让树不长高
①用根结点的绝对值表示树的结点的总数
②Union操作,让小树合并到大树

// Union 并操作,小树合并到大树 时间复杂度O(log2(n))
void Union(int S[],int Root1,int Root2){if(Root1==Root2) return;if(S[Root2]>S[Root1]){  // Root2 结点数更少S[Root1] += S[Root2];  // 累加结点总数S[Root2] = Root1;  // 小树合并大树} else{S[Root2] += S[Root1];S[Root1] = Root2;}
}

Find 操作的优化(压缩路径)

优化思路:先找到根结点,再将查找路径上所有结点都挂到根结点上

int Find(int S[],int x){int root = x;while(S[root]>=0)  root=S[root];  // 循环找到根while(x!=root){  // 压缩路径int t=S[x];  // t指向x的父节点S[x] = root; // x直接挂到根结点上x=t;}return root;  // 返回根结点编号
}

相关文章:

数据结构详细笔记——并查集

文章目录 逻辑结构存储结构并、查代码实现Union 操作的优化Find 操作的优化&#xff08;压缩路径&#xff09; 逻辑结构 集合&#xff1a;将各个元素划分为若干个互不相交的子集的集合 森林是m(m>0)棵互不相交的树的集合 存储结构 #define SIZE 13 int UFSets[SIZE]; …...

transformers-Generation with LLMs

https://huggingface.co/docs/transformers/main/en/llm_tutorialhttps://huggingface.co/docs/transformers/main/en/llm_tutorial停止条件是由模型决定的&#xff0c;模型应该能够学习何时输出一个序列结束&#xff08;EOS&#xff09;标记。如果不是这种情况&#xff0c;则在…...

maven之父子工程版本控制案例实战,及拓展groupId和artifactId的含义

<parent>标签 用于父子工程项目&#xff0c;什么是父子工程&#xff1f; 顾名思义&#xff0c;maven父子项目是一个有一个父项目&#xff0c;父项目下面又有很多子项目的maven工程&#xff0c;当然&#xff0c;子项目下面还可以添加子项目&#xff0c;从而形成一个树形…...

100量子比特启动实用化算力标准!玻色量子重磅发布相干光量子计算机

2023年5月16日&#xff0c;北京玻色量子科技有限公司&#xff08;以下简称“玻色量子”&#xff09;在北京正大中心成功召开了2023年首场新品发布会&#xff0c;重磅发布了自研100量子比特相干光量子计算机——“天工量子大脑”。 就在3个月前&#xff0c;因“天工量子大脑”在…...

JAVA基础(JAVA SE)学习笔记(十)多线程

前言 1. 学习视频&#xff1a; 尚硅谷Java零基础全套视频教程(宋红康2023版&#xff0c;java入门自学必备)_哔哩哔哩_bilibili 2023最新Java学习路线 - 哔哩哔哩 第三阶段&#xff1a;Java高级应用 9.异常处理 10.多线程 11.常用类和基础API 12.集合框架 13.泛型 14…...

ChatGPT参数只有200亿?扩散代码模型,意外泄露

微软的研究部门发布了一篇关于预训练扩散代码模型CodeFusion的论文。在展示代码生成任务的基线数据对比时&#xff0c;发现了一个有趣的事情&#xff0c;ChatGPT&#xff08;gpt-3.5-turbo&#xff09;的参数只有200亿。 要知道&#xff0c;gpt-3.5-turbo是OpenAI中应用最多、…...

VR虚拟仿真教学在建筑学课堂中的应用

1. 增强真实感&#xff1a;VR技术能创造出近乎真实的虚拟环境&#xff0c;使学生仿佛置身其中&#xff0c;增强他们的感官体验。 2. 打破空间限制&#xff1a;VR教学可以打破时间和空间的限制&#xff0c;学生可以在任何时间、任何地点进行学习&#xff0c;无需担心课堂位置的…...

竞赛 深度学习实现行人重识别 - python opencv yolo Reid

文章目录 0 前言1 课题背景2 效果展示3 行人检测4 行人重识别5 其他工具6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习的行人重识别算法研究与实现 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c…...

当代都市的时尚先锋:气膜建筑的魅力

当代城市的崛起如一部快速奔腾的时光流。在这个光速发展的都市中&#xff0c;时间被看作珍贵的黄金&#xff0c;而效率被视为无价的生命。而在这个节奏日益加快的现代都市背后&#xff0c;一个独特的“神器”——气膜建筑&#xff0c;悄然崭露头角&#xff0c;成为城市发展的领…...

品牌加盟商做信息展示预约小程序的效果如何

很多行业都有中部或头部品牌&#xff0c;对实体品牌企业来说想要快速高效发展&#xff0c;除了多地直营店外还需要招募加盟商进而提升生意营收。 因此线上渠道变得尤为重要&#xff0c;除了网站外&#xff0c;小程序是连接多平台生态很好的工具&#xff0c;随时打开、直接触达…...

delphi 11.3 FastReport 多设备跨平台 打印之解决方法

以下能WINDOWS10 DELPHI 11.3 FastReport6.0上顺利通过 FastReport6.2对Multi-Device Application应用的支持不够友好&#xff0c;如下图&#xff1b;在palette FastReport6.0才出现几个制件。 非Multi-Device Application应用时是一大堆&#xff1b; 非Multi-Device Appl…...

配置vue 环境

一、安装Node.js及配置环境 环境变量配置 第一步&#xff1a;“此电脑”-右键-“属性”-“高级系统设置”-“高级”-“环境变量” 第二步&#xff08;我的为&#xff1a;C:\Program Files\nodejs &#xff09;&#xff0c;然后编辑path&#xff0c;新建&#xff0c;为&#xf…...

Visio文件编辑查看工具Visio Viewer for Mac

Visio Viewer mac版是一款Visio文件查看工具&#xff0c;可以使用本程序打开所有的visio文件数据&#xff0c;支持多种语言环境&#xff0c;可以对visio文件进行编辑、跳转参数等设置。 Visio Viewer for Mac可以打开和查看Visio文件&#xff08;.vsd、.vdx和.vsdm文件&#x…...

现在软文发布平台都有哪些?如何在正规媒体发稿?

近年来,随着广告行业竞争愈加激烈,越来越多的企业开始注重软文宣传。软文推广平台是企业在网络上发布软文、传播信息和推广产品的重要工具。 媒介易软文平台介绍更好的品牌宣传和市场推广&#xff1a;软文推广发稿有哪些平台&#xff0c; 软文发稿好方法&#xff1f;软文不仅能…...

【卷积神经网络】YOLO 算法原理

在计算机视觉领域中&#xff0c;目标检测&#xff08;Object Detection&#xff09;是一个具有挑战性且重要的新兴研究方向。目标检测不仅要预测图片中是否包含待检测的目标&#xff0c;还需要在图片中指出它们的位置。2015 年&#xff0c;Joseph Redmon, Santosh Divvala 等人…...

云计算与ai人工智能对高防cdn的发展

高防CDN&#xff08;Content Delivery Network&#xff09;作为网络安全领域的一项关键技术&#xff0c;致力于保护在线内容免受各种网络攻击&#xff0c;包括分布式拒绝服务攻击&#xff08;DDoS&#xff09;等。然而&#xff0c;随着人工智能&#xff08;AI&#xff09;和大数…...

Web3时代:探索DAO的未来之路

Web3 的兴起不仅代表着技术进步&#xff0c;更是对人类协作、创新和价值塑造方式的一次重大思考。在 Web3 时代&#xff0c;社区不再仅仅是共同兴趣的聚集点&#xff0c;而变成了一个价值交流和创新的平台。 去中心化&#xff1a;超越技术的革命 去中心化不仅仅是 Web3 的技术…...

odbcinst文件

odbcinst文件是ODBC&#xff08;Open Database Connectivity&#xff09;驱动程序管理器的配置文件。ODBC是一种标准的数据库访问接口&#xff0c;允许应用程序通过统一的方式连接和访问不同类型的数据库。 odbcinst文件通常位于操作系统的特定目录中&#xff0c;并且用于定义…...

(CQUPT 的某数据结构homework)

CQUPT 的某数据结构homework 基于线性表的图书信息管理基于栈的算术表达式求值基于字符串模式匹配算法的病毒感染检测问题 基于哈夫曼树的数据压缩算法基于二叉树的表达式求值算法基于 Dijsktra 算法的最短路基于广度优先搜索的六度空间排序算法的实现与分析 基于线性表的图书信…...

Android页面周期、页面跳转

1.什么是Activity&#xff1f; Activity是Android的四大组件之一&#xff0c;它是一种可以包含用户界面的组件&#xff0c;主要用于和用户进行交互。Activity用于显示用户界面&#xff0c;用户通过Activity交互完成相关操作&#xff0c;一个APP允许有多个Activity。 2.Activi…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...