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

并查集的模拟实现

简化版本


class UnionFindSet
{
public:UnionFindSet(size_t n):_ufs(n, -1){}void Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);// 如果本身就在一个集合就没必要合并了if (root1 == root2)return;// 控制数据量小的往大的集合合并if (abs(_ufs[root1]) < abs(_ufs[root2]))swap(root1, root2);_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}int FindRoot(int x){int root = x;while (_ufs[root] >= 0){root = _ufs[root];}// 路径压缩while (_ufs[x] >= 0){int parent = _ufs[x];_ufs[x] = root;x = parent;}return root;}bool InSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}size_t SetSize(){size_t size = 0;for (size_t i = 0; i < _ufs.size(); ++i){if (_ufs[i] < 0){++size;}}return size;}private:vector<int> _ufs;
};

相关文章:

并查集的模拟实现

简化版本 class UnionFindSet { public:UnionFindSet(size_t n):_ufs(n, -1){}void Union(int x1, int x2){int root1 FindRoot(x1);int root2 FindRoot(x2);// 如果本身就在一个集合就没必要合并了if (root1 root2)return;// 控制数据量小的往大的集合合并if (abs(_ufs[roo…...

如何高效删除 MySQL 日志表中的历史数据?实战指南

在处理高并发的物联网平台或者其他日志密集型应用时&#xff0c;数据库中的日志表往往会迅速增长&#xff0c;数据量庞大到数百GB甚至更高&#xff0c;严重影响数据库性能。如何有效管理这些庞大的日志数据&#xff0c;特别是在不影响在线业务的情况下&#xff0c;成为了一项技…...

请散户股民看过来,密切关注两件大事

明天股市要开市&#xff0c;不仅散户股民期盼节后股市大涨&#xff0c;上面也同样想在节后来上一个“开门红”。 为此&#xff0c;上面没休假&#xff0c;关起门来办了两件大事&#xff0c;这两天发布消息已提前预热了。 两件大事如下&#xff1a; 一是&#xff0c;上交所10…...

设计模式之外观模式(Facade)

一、外观模式介绍 外观模式( Facade Pattern)&#xff0c;也叫门面模式&#xff0c;是一个 “结构型” 设计模式。 外观模式的原始定义是&#xff1a;为子系统中的一组接口提供统一的接口。它定义了一个更高级别 的接口&#xff0c;使子系统更易于使用。 外观模式&#xff0c;是…...

解锁 Python 嵌套字典的奥秘:高效操作与实战应用指南

文章目录 前言&#x1f340;一、 什么是 Python 字典&#xff1f;1.1 字典的语法 &#x1f340;二、 字典的基本操作2.1 字典的创建2.2 访问字典中的值2.3 添加或修改键值对2.4 删除字典中的键值对 &#x1f340;三、 字典的遍历操作3.1 遍历字典的键3.2 遍历字典的值3.3 同时遍…...

联想服务器配置阵列、安装操作系统

文章目录 [toc]1.配置阵列2.制作启动盘3.安装系统 1.配置阵列 1.根据提示进入BIOS设置&#xff08;F1&#xff09; 2.系统设置 3.存储 4.第四步可以看到raid卡信息 5.Main Menu 6.Configuration Management 7.Create Virtual Drive 8.Select RAID Level raid5 9.Select Drives…...

【深度强化学习】DDPG实现的4个细节(OUNoise等)

文章目录 前言一、论文内容简述创新点&#xff08;特点&#xff0c;与DQN的区别&#xff09;&#xff1a;可借鉴参数&#xff1a;细节补充&#xff1a; 二、细节1&#xff1a;weight_decay原理代码 三、细节2&#xff1a;OUNoise原理代码 四、细节3&#xff1a;ObsNorm原理代码…...

算法工程师重生之第二十二天(递增子序列 全排列 全排列 II 重新安排行程 N皇后 解数独 总结 )

参考文献 代码随想录 一、非递减子序列 给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素&#xff0c;如出现两个整数相等&#xff0c;也可以视作…...

css的选择器及优先级

一、css选择器 CSS选择器是用来选择HTML文档中的元素&#xff0c;并为它们应用样式规则的工具。CSS选择器有很多种&#xff0c;可以根据元素的类名、ID、属性、伪类、伪元素、标签等来选择元素。以下是一些常见的CSS选择器及其用法&#xff1a; 1. ID选择器&#xff1a; 根据…...

JavaScript中的数组不改变原数组的方法

数组 var a [1, 2, 3, 5, 8, 13, 21] 不改变原数组的方法 length 数组元素的长度 继承自原型 concat(arrayX,arrayY) 合并两个或多个数组&#xff0c;返回新数组 合并&#xff0c;a.concat(b) var a[1,2,3],b[4,5,6],c[7,8,9]; a.concat(b,c); //[1, 2, 3, 4, 5, 6, 7…...

Go语言实现长连接并发框架 - 路由分组

文章目录 前言接口结构体接口实现项目地址最后 前言 你好&#xff0c;我是醉墨居士&#xff0c;我们上篇博客实现了任务执行流的路由模块&#xff0c;接下来我们实现一下对任务执行流进行任务 接口 trait/router_group.go type RouterGroup interface {RouterGroup(flow ..…...

跨 VLAN 通信

跨 VLAN 通信指的是不同 VLAN 之间的网络设备进行数据交换的能力。由于 VLAN 将网络分割成多个逻辑隔离的广播域&#xff0c;默认情况下&#xff0c;不同 VLAN 之间的设备无法直接通信。为了实现跨 VLAN 通信&#xff0c;需要借助一些网络设备和技术。以下详细讲解跨 VLAN 通信…...

11.4 Linux_线程_条件变量

概述 条件变量的作用&#xff1a; 条件变量和互斥量配合使用&#xff0c;主要应用于生产者和消费者问题。 这种问题也是一种临界资源的问题&#xff0c;但与互斥量一文中 "写文件" 这种资源不同。文件是一直存在的临界资源&#xff0c;而生产者的资源不是一直存在…...

通信工程学习:什么是IP网际协议

IP&#xff1a;网际协议 IP网际协议&#xff08;Internet Protocol&#xff0c;简称IP&#xff09;是整个TCP/IP协议栈中的核心协议之一&#xff0c;它负责在网络中传送数据包&#xff0c;并提供寻址和路由功能。以下是对IP网际协议的详细解释&#xff1a; 一、对IP网际协议的…...

github 国内文件加速下载

参看;https://www.cnblogs.com/ting1/p/18356265 在源网址前加上 https://hub.gitmirror.com/ 或https://mirror.ghproxy.com/&#xff0c;例如&#xff1a; https://hub.gitmirror.com/https://github.com/t1m0thyj/WinDynamicDesktop/releases/download/v5.4.1/WinDynamicD…...

算法6:模拟运算

文章目录 z字形变幻外观数列数青蛙 题目均来自于力扣 z字形变幻 class Solution { public:string convert(string s, int numRows) {int n s.size();if(n < numRows || numRows 1) return s;int d 2 * numRows - 2;string res;for(int j 0; j < n; j d){res s[j]; …...

【网络协议大花园】应用层 http协议的使用小技巧,用好了都不用加班,效率翻两倍(上篇)

本篇会加入个人的所谓鱼式疯言 ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人…...

今日指数day8实战补充(上)

1.用户管理 1.多条件综合查询 1.1 多条件综合查询接口说明 1&#xff09;原型效果 2&#xff09;接口说明 功能描述&#xff1a;多条件综合查询用户分页信息&#xff0c;条件包含&#xff1a;分页信息 用户创建日期范围 服务路径&#xff1a;/api/users 服务方法&#xff1…...

Python 之进阶语法:with...as...

1. Python with…as…是什么 Python 的 with…as… 语句&#xff0c;就像一个贴心的管家&#xff0c;负责照顾你的资源&#xff0c;让你不再担心忘记关闭文件、网络连接或数据库事务等。这个管家在你进入“房间”时自动打开门&#xff0c;离开时帮你把门关上&#xff0c;真的是…...

嵌入式硬件设计知识详解

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

保姆级避坑指南:用STM32F103C8T6+ESP8266(AT指令)做WiFi遥控小车,我踩过的那些坑

STM32F103C8T6ESP8266 WiFi遥控小车避坑实战手册 1. 硬件选型与连接&#xff1a;那些容易被忽视的细节 在开始任何代码编写之前&#xff0c;硬件连接的正确性往往决定了项目的成败。使用STM32F103C8T6&#xff08;俗称"蓝莓板"&#xff09;与ESP8266模块组合时&#…...

基于HTML5 Canvas的轻量级图像标注库visual-annotator集成指南

1. 项目概述&#xff1a;一个为开发者打造的视觉标注利器如果你做过图像识别、目标检测或者任何需要处理大量图片标注的计算机视觉项目&#xff0c;那你一定对标注工具不陌生。从早期的LabelImg到后来的CVAT、Label Studio&#xff0c;工具的选择往往决定了你项目前期数据准备的…...

ESP-SR深度解析:嵌入式语音识别系统的架构设计与性能优化实战指南

ESP-SR深度解析&#xff1a;嵌入式语音识别系统的架构设计与性能优化实战指南 【免费下载链接】esp-sr Speech recognition 项目地址: https://gitcode.com/gh_mirrors/es/esp-sr 在物联网设备智能化浪潮中&#xff0c;语音交互已成为人机交互的重要入口。ESP-SR作为乐鑫…...

赛车电气系统设计的现代化转型与实践

1. 赛车电气系统设计的现状与挑战当人们谈论赛车技术时&#xff0c;脑海中浮现的往往是碳纤维车身、空气动力学套件或是大马力发动机。但在这光鲜亮丽的表象背后&#xff0c;电气系统才是现代赛车的"神经系统"。有趣的是&#xff0c;这个关键领域的设计方法却呈现出两…...

复杂系统交付中的风险治理与经济模型转型

1. 复杂系统交付中的风险本质与治理转型在航空航天、国防军工等复杂系统开发领域&#xff0c;项目失败率长期居高不下。根据IBM对全球500个大型系统的调研&#xff0c;73%的项目存在严重进度延迟&#xff0c;平均超支达到原始预算的189%。这种系统性失效的根源在于传统工程治理…...

我的嵌入式项目踩坑记:用STM32的输入捕获功能给自制旋转编码器“把脉”

我的嵌入式项目踩坑记&#xff1a;用STM32的输入捕获功能给自制旋转编码器“把脉” 去年参加电子设计竞赛时&#xff0c;我遇到了一个棘手的问题——自制的旋转编码器信号抖动严重&#xff0c;导致电机转速测量误差高达15%。作为一名嵌入式开发者&#xff0c;这种精度显然无法接…...

FPGA驱动ADS1256的ADC精度优化实战(三)

1. 硬件连接优化&#xff1a;从杜邦线到PCB布局的精度跃升 第一次用杜邦线连接FPGA和ADS1256时&#xff0c;我测得的电压误差居然有30mV&#xff0c;这让我差点怀疑人生。后来把万用表直接怼到ADC引脚上&#xff0c;才发现杜邦线本身就有5-8mV的压降波动。这种看似微不足道的干…...

书成紫微动,律定凤凰驯:海棠山铁哥的道,从来不是嘴上说的,是写在作品里的

文坛从不缺大道理&#xff0c;也不缺高谈阔论的传道者&#xff0c;历来最缺的&#xff0c;是知行合一、落地成真的真大道。一、乱象&#xff1a;言道者多&#xff0c;行道者少口头标榜实际行径文脉传承随波逐流初心坚守妥协功利拒绝流量收割热度敬畏真诚唯数据论 语言可以伪装人…...

打卡信奥刷题(3271)用C++实现信奥题 P8855 [POI 2002 R1] 商务旅行

P8855 [POI 2002 R1] 商务旅行 题目描述 某地首都的商人要经常到其他城镇去做生意&#xff0c;他们会按自己的路线去走。 有 NNN 个城镇&#xff0c;首都编号为 111。商人从首都出发&#xff0c;其他各城镇之间都有道路连接。 任意两个城镇之间如果有直连道路&#xff0c;在他们…...

从YOLOv5到Detectron2:COCO数据集在不同CV框架下的加载与预处理实战

从YOLOv5到Detectron2&#xff1a;COCO数据集跨框架加载与预处理实战指南 在计算机视觉领域&#xff0c;COCO数据集已成为目标检测和实例分割任务的事实标准。但对于开发者而言&#xff0c;面对PyTorch生态中YOLOv5、MMDetection和Detectron2等不同框架时&#xff0c;数据加载和…...