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

acwing算法基础之数据结构--并查集算法

目录

  • 1 基础知识
  • 2 模板
  • 3 工程化

1 基础知识

并查集支持O(1)时间复杂度实现:

  1. 将两个集合合并。
  2. 询问两个元素是否在一个集合中。

基本原理:每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个结点存储它的父结点,p[x]表示x的父结点。

问题1:如何判断树根:p[x] == x
问题2:如何求x的集合编号:while (p[x] != x) x = p[x];。上述为朴素做法,可以通过路径压缩,进行优化。

int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}

问题3:如何合并两个集合:px是x的集合编号,py是y的集合编号:p[px] = py

2 模板

(1)朴素并查集:int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化,假定节点编号是1~nfor (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合:p[find(a)] = find(b);(2)维护size的并查集:int p[N], size[N];//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];}// 初始化,假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;size[i] = 1;}// 合并a和b所在的两个集合:size[find(b)] += size[find(a)];p[find(a)] = find(b);(3)维护到祖宗节点距离的并查集:int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点int find(int x){if (p[x] != x){int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}// 初始化,假定节点编号是1~nfor (int i = 1; i <= n; i ++ ){p[i] = i;d[i] = 0;}// 合并a和b所在的两个集合:p[find(a)] = find(b);d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

3 工程化

class UnionFind {
public:UnionFind(int n) {this->n = n;p.resize(n);cnt.resize(n);d.resize(n);for (int i = 0; i < n; ++i) {p[i] = i;cnt[i] = 1;d[i] = 0;}}int find(int x) {if (x != p[x]) {int u = find(p[x]);d[x] += d[p[x]];p[x] = u;}return p[x];}void merge(int x, int y) {int px = find(x), py = find(y);if (px != py) {p[px] = py;cnt[py] += cnt[px];		}return;}int size(int x) {//返回x所在集合的大小return cnt[find(x)];}
private:int n;vector<int> p; //存储父结点vector<int> cnt; //存储集合大小,根结点的cnt才有意义vector<int> d; //存储到根结点的距离
};

相关文章:

acwing算法基础之数据结构--并查集算法

目录 1 基础知识2 模板3 工程化 1 基础知识 并查集支持O(1)时间复杂度实现&#xff1a; 将两个集合合并。询问两个元素是否在一个集合中。 基本原理&#xff1a;每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个结点存储它的父结点&#xff0c;p[x]表示x的父结点…...

k8s:二进制搭建 Kubernetes v1.20

目录 1 操作系统初始化配置 2 部署 etcd 集群 2.1 准备签发证书环境 2.2 生成Etcd证书 3 部署 docker引擎 4 部署 Master 组件 5 部署 Worker Node 组件 k8s集群master01&#xff1a;192.168.30.105 kube-apiserver kube-controller-manager kube-scheduler etcd k8s集…...

SpringBoot系列-1启动流程

背景 本文作为SpringBoot系列的开篇&#xff0c;介绍SpringBoot的启动流程&#xff0c;包括Spring容器和Tomcat启动过程。SpringBoot作为流行的微服务框架&#xff0c;其是基于约定和自动装配机制对Spring的封装和增强。 由于前面的Spring系列对Spring容器已经进行了较为细致的…...

【记】一次common模块导入无效的bug

首先Maven clean install无用 然后idea清除缓存重启无用 pom.xml文件重载无效 正确解决路径&#xff1a; 1.检查common模块的父工程导入和自身模块的声明是否正确 默认是继承父工程的groupid&#xff0c;可以不用再声明 2.检查子工程是否引入正确的common&#xff0c;org不要…...

1.Netty概述

原生NIO存在的问题(Netty要解决的问题) 虽然JAVA NIO 和 JAVA AIO框架提供了多路复用IO/异步IO的支持&#xff0c;但是并没有提供给上层“信息格式”的良好封装。JAVA NIO 的 API 使用麻烦,需要熟练掌握 ByteBuffer、Channel、Selector等 , 所以用这些API实现一款真正的网络应…...

YOLO目标检测——真实道路车辆检测数据集【含对应voc、coco和yolo三种格式标签】

实际项目应用&#xff1a;自动驾驶技术研发、交通安全监控数据集说明&#xff1a;真实道路车辆检测数据集&#xff0c;真实场景的高质量图片数据&#xff0c;数据场景丰富标签说明&#xff1a;使用lableimg标注软件标注&#xff0c;标注框质量高&#xff0c;含voc(xml)、coco(j…...

【Solidity】Solidity中的基本数据类型和复合数据类型

1. 基本数据类型 1.1 整数类型 Solidity支持有符号整数和无符号整数&#xff0c;可以指定位数和范围。以下是一些整数类型的示例&#xff1a; int&#xff1a;有符号整数&#xff0c;可以是正数或负数。2&#xff0c;-45&#xff0c;2023 uint&#xff1a;无符号整数&#x…...

Flutter Set存储自定义对象时 如何保证唯一

在Flutter中&#xff0c;Set和List是两种不同的集合类型&#xff0c;List中存储的元素可以重复&#xff0c;Set中存储的元素不可重复。 如果你想在Set中存储自定义对象&#xff0c;你需要确保对象的唯一性。 这可以通过在自定义类中实现hashCode方法和equals方法来实现。 has…...

Docker容器中执行throttle.sh显示权限报错:RTNETLINK answers: Operation not permitted

在模拟通信环境时&#xff0c;我执行了一下命令&#xff1a; bash ./throttle.sh wan但是&#xff0c;出现了权限的报错&#xff1a;RTNETLINK answers: Operation not permitted 解决方案说简单也挺简单&#xff0c;只需要两步完成。但是其实又蛮繁琐&#xff0c;因为需要将…...

【Linux】jdk、tomcat、MySQL环境搭建的配置安装,Linux更改后端端口

一、作用 工具的组合为开发者和系统管理员提供了构建和运行Java应用程序以及存储和管理数据的完整环境。 JDK&#xff08;Java Development Kit&#xff09;&#xff1a;JDK是Java开发工具包&#xff0c;它提供了开发和运行Java应用程序所需的工具和库。通过安装JDK&#xff0c…...

【WinForm详细教程七】WinForm中的DataGridView控件

文章目录 1.主要属性DataSource行&#xff08;Row 相关属性&#xff09;列&#xff08;Column 相关属性&#xff09;单元格&#xff08;Cell 相关属性&#xff09;逻辑删除AllowUserToAddRowsAllowUserToDeleteRowsAllowUserToOrderColumns其他布局和行为属性 2.控件中的行、列…...

SpringCloudTencent(上)

SpringCloudTencent 1.PolarisMesh介绍2.北极星具备的功能3.北极星包含的组件4.功能特性1.服务管理1.服务注册2.服务发现3.健康检查 2.配置管理 5.代码实战1.环境准备2.服务注册与发现3.远程调用 1.PolarisMesh介绍 1.北极星是腾讯开源的服务治理平台&#xff0c;致力于解决分…...

linux硬盘挂载(linux 修改某个磁盘挂载到新目录)

文章目录 什么是硬盘挂载linux 修改某个磁盘挂载到新目录 什么是硬盘挂载 在Linux操作系统中&#xff0c;挂载硬盘是将硬盘的分区或者整个硬盘与文件系统关联起来&#xff0c;使得我们可以通过文件系统访问硬盘中的数据。 确认硬盘信息 sudo fdisk -l该命令会列出所有已连接…...

hdlbits系列verilog解答(always块case语句)-33

文章目录 一、问题描述二、verilog源码三、仿真结果一、问题描述 Verilog 中的 case 语句几乎等同于 if-elseif-else 序列,该序列将一个表达式与其他表达式列表进行比较。它的语法和功能与 C 中的 switch 语句不同。 always @(*) begin // This is a combinational circuit …...

3D医学三维技术影像PACS系统源码

一、系统概述 3D医学影像PACS系统&#xff0c;它集影像存储服务器、影像诊断工作站及RIS报告系统于一身,主要有图像处理模块、影像数据管理模块、RIS报告模块、光盘存档模块、DICOM通讯模块、胶片打印输出等模块组成&#xff0c; 具有完善的影像数据库管理功能&#xff0c;强大…...

python 之softmx 函数

文章目录 总的介绍小应用 总的介绍 Softmax函数是一个常用的激活函数&#xff0c;通常用于多类别分类问题中。它将一个实数向量转换为概率分布。这个函数的输出是一个概率分布&#xff0c;表示输入样本属于每个可能类别的概率。 给定一个具有 (K) 个不同数值的实数向量 z (z1…...

第3章_基本select语句

文章目录 SQL概述SQL背景知识SQL分类 SQL语言的规则与规范SQL语言的规则SQL大小写规范注释命令规则&#xff08;暂时了解&#xff09;数据导入指令 基本的select语句select ...select ... from列的别名去除重复行空值参与运算着重号查询常数 显示表结构讲课代码课后练习 SQL概述…...

GPT3.5+文心一言+chatGLM 计算和代码生成能力简单对比

chatGLM3刚发布&#xff08;10.27&#xff09;&#xff0c;打算尝试一下其code和计算能力。 共选取三个问题&#xff0c;难度从中等&#xff0c;偏困难&#xff0c;到困难。测试内容是正好手头上在做的事想让LLM来完成&#xff08;偷懒&#xff09;&#xff0c;之前都是直接使…...

手搓一个ubuntu自动安装python3.9的sh脚本

#!/bin/bash# Step 1: 更新系统软件包 sudo apt update sudo apt upgrade -y sudo apt install -y software-properties-common# Step 2: 安装Python 3.9的依赖项 sudo apt install -y build-essential zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libread…...

volte使用方法 nodejs版本切换

Volta 一种轻松管理 JavaScript 命令行工具的方法。 文档 https://docs.volta.sh/guide/ 源码 https://github.com/volta-cli/volta 命令行 安装版本 此方法运行完会配置为默认版本 volta install node 安装最新版本的node volta install node14 安装指定版本的node volta i…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...