数据结构详细笔记——并查集
文章目录
- 逻辑结构
- 存储结构
- 并、查代码实现
- 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 操作的优化(压缩路径) 逻辑结构 集合:将各个元素划分为若干个互不相交的子集的集合 森林是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停止条件是由模型决定的,模型应该能够学习何时输出一个序列结束(EOS)标记。如果不是这种情况,则在…...
maven之父子工程版本控制案例实战,及拓展groupId和artifactId的含义
<parent>标签 用于父子工程项目,什么是父子工程? 顾名思义,maven父子项目是一个有一个父项目,父项目下面又有很多子项目的maven工程,当然,子项目下面还可以添加子项目,从而形成一个树形…...
100量子比特启动实用化算力标准!玻色量子重磅发布相干光量子计算机
2023年5月16日,北京玻色量子科技有限公司(以下简称“玻色量子”)在北京正大中心成功召开了2023年首场新品发布会,重磅发布了自研100量子比特相干光量子计算机——“天工量子大脑”。 就在3个月前,因“天工量子大脑”在…...
JAVA基础(JAVA SE)学习笔记(十)多线程
前言 1. 学习视频: 尚硅谷Java零基础全套视频教程(宋红康2023版,java入门自学必备)_哔哩哔哩_bilibili 2023最新Java学习路线 - 哔哩哔哩 第三阶段:Java高级应用 9.异常处理 10.多线程 11.常用类和基础API 12.集合框架 13.泛型 14…...
ChatGPT参数只有200亿?扩散代码模型,意外泄露
微软的研究部门发布了一篇关于预训练扩散代码模型CodeFusion的论文。在展示代码生成任务的基线数据对比时,发现了一个有趣的事情,ChatGPT(gpt-3.5-turbo)的参数只有200亿。 要知道,gpt-3.5-turbo是OpenAI中应用最多、…...
VR虚拟仿真教学在建筑学课堂中的应用
1. 增强真实感:VR技术能创造出近乎真实的虚拟环境,使学生仿佛置身其中,增强他们的感官体验。 2. 打破空间限制:VR教学可以打破时间和空间的限制,学生可以在任何时间、任何地点进行学习,无需担心课堂位置的…...
竞赛 深度学习实现行人重识别 - python opencv yolo Reid
文章目录 0 前言1 课题背景2 效果展示3 行人检测4 行人重识别5 其他工具6 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 **基于深度学习的行人重识别算法研究与实现 ** 该项目较为新颖,适合作为竞赛课题方向,…...
当代都市的时尚先锋:气膜建筑的魅力
当代城市的崛起如一部快速奔腾的时光流。在这个光速发展的都市中,时间被看作珍贵的黄金,而效率被视为无价的生命。而在这个节奏日益加快的现代都市背后,一个独特的“神器”——气膜建筑,悄然崭露头角,成为城市发展的领…...
品牌加盟商做信息展示预约小程序的效果如何
很多行业都有中部或头部品牌,对实体品牌企业来说想要快速高效发展,除了多地直营店外还需要招募加盟商进而提升生意营收。 因此线上渠道变得尤为重要,除了网站外,小程序是连接多平台生态很好的工具,随时打开、直接触达…...
delphi 11.3 FastReport 多设备跨平台 打印之解决方法
以下能WINDOWS10 DELPHI 11.3 FastReport6.0上顺利通过 FastReport6.2对Multi-Device Application应用的支持不够友好,如下图;在palette FastReport6.0才出现几个制件。 非Multi-Device Application应用时是一大堆; 非Multi-Device Appl…...
配置vue 环境
一、安装Node.js及配置环境 环境变量配置 第一步:“此电脑”-右键-“属性”-“高级系统设置”-“高级”-“环境变量” 第二步(我的为:C:\Program Files\nodejs ),然后编辑path,新建,为…...
Visio文件编辑查看工具Visio Viewer for Mac
Visio Viewer mac版是一款Visio文件查看工具,可以使用本程序打开所有的visio文件数据,支持多种语言环境,可以对visio文件进行编辑、跳转参数等设置。 Visio Viewer for Mac可以打开和查看Visio文件(.vsd、.vdx和.vsdm文件&#x…...
现在软文发布平台都有哪些?如何在正规媒体发稿?
近年来,随着广告行业竞争愈加激烈,越来越多的企业开始注重软文宣传。软文推广平台是企业在网络上发布软文、传播信息和推广产品的重要工具。 媒介易软文平台介绍更好的品牌宣传和市场推广:软文推广发稿有哪些平台, 软文发稿好方法?软文不仅能…...
【卷积神经网络】YOLO 算法原理
在计算机视觉领域中,目标检测(Object Detection)是一个具有挑战性且重要的新兴研究方向。目标检测不仅要预测图片中是否包含待检测的目标,还需要在图片中指出它们的位置。2015 年,Joseph Redmon, Santosh Divvala 等人…...
云计算与ai人工智能对高防cdn的发展
高防CDN(Content Delivery Network)作为网络安全领域的一项关键技术,致力于保护在线内容免受各种网络攻击,包括分布式拒绝服务攻击(DDoS)等。然而,随着人工智能(AI)和大数…...
Web3时代:探索DAO的未来之路
Web3 的兴起不仅代表着技术进步,更是对人类协作、创新和价值塑造方式的一次重大思考。在 Web3 时代,社区不再仅仅是共同兴趣的聚集点,而变成了一个价值交流和创新的平台。 去中心化:超越技术的革命 去中心化不仅仅是 Web3 的技术…...
odbcinst文件
odbcinst文件是ODBC(Open Database Connectivity)驱动程序管理器的配置文件。ODBC是一种标准的数据库访问接口,允许应用程序通过统一的方式连接和访问不同类型的数据库。 odbcinst文件通常位于操作系统的特定目录中,并且用于定义…...
(CQUPT 的某数据结构homework)
CQUPT 的某数据结构homework 基于线性表的图书信息管理基于栈的算术表达式求值基于字符串模式匹配算法的病毒感染检测问题 基于哈夫曼树的数据压缩算法基于二叉树的表达式求值算法基于 Dijsktra 算法的最短路基于广度优先搜索的六度空间排序算法的实现与分析 基于线性表的图书信…...
Android页面周期、页面跳转
1.什么是Activity? Activity是Android的四大组件之一,它是一种可以包含用户界面的组件,主要用于和用户进行交互。Activity用于显示用户界面,用户通过Activity交互完成相关操作,一个APP允许有多个Activity。 2.Activi…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
