当前位置: 首页 > 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…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...