并查集(基础学习与应用)

在这里插入图片描述

并查集

基本原理:

对于多个集合,每个集合中的多个元素用一颗树的形式表示,根节点的编号即为整个集合的编号,每个树上节点存储其父节点,使得当前集合的每个子节点都可以通过对父节点的询问来找到根节点,根节点的父节点为其本身。

本文中 f [ x ] f[x] f[x]表示 x x x点的父节点。

并查集的作用:

  1. 判断当前点是否为当前集合的根节点,即 i f ( f [ x ] = = x ) if(f[x] == x) if(f[x]==x)时,当前点为所属集合的根节点

  2. 求取当前点的集合编号(根节点),即 w h i l e ( f [ x ] ! = x ) x = f [ x ] while(f[x] != x) x = f[x] while(f[x]!=x)x=f[x],直到找到根节点

    优化点:通过路径压缩,可以实现一次遍历,使得路径上所有节点均指向集合根节点,减少后续遍历次数

  3. 合并两集合,即将其中一个集合的根节点作为另一个集合的根节点的父节点,即 f [ x ] = f [ y ] f[x] = f[y] f[x]=f[y]

基础操作:

int find(int x)//返回x所在集合的编号,即x的根节点,用路径压缩优化
{	if(f[x] != x) f[x] = find(f[x]);//如何p[x]非根节点,则由父节点继续向上查找return f[x];//根节点
}

基础运用:求连通块中点的数量

#include<iostream>
#include<algorithm>
using namespace std;const int N = 2e5+10;int f[N], n, m;
int st[N];int find(int x) {if(f[x] != x) f[x] = find(f[x]);return f[x];
}int main() {cin >> n >> m;for(int i = 1; i <= n; i ++) {f[i] = i;//各集合初始化,各自一个集合st[i] = 1;//各自独立集合的数量为1}while(m --) {string op; cin >> op;int a, b;if(op[0] == 'C'){//连接操作cin >> a >> b;if(find(a) == find(b)) continue; //若ab已在同一根节点下无需操作//顺序不能搞反st[find(b)] += st[find(a)];//a的集合归b则b集合要加上a集合f[find(a)] = find(b);//将a的根节点连接到b的根节点之下}else if(op[1] == '1'){//询问ab是否在同一集合当中,即是否在同一联通块当中cin >> a >> b;if(find(a) == find(b)) puts("YES");else puts("NO");} else {//询问a所在集合的大小,即联通块的数量cin >> a;cout << st[find(a)] << endl;}}return 0;
}

增补应用:求取带权并查集

//在每条边添加权值
int find(int x){if(f[x] != x){int u = find(f[x]);value[x] += value[f[x]];f[x] = u;}return f[x];
}//两个点
int pa = find(a);
int pb = find(b);
if(pa != pb){p[pa] = pb;value[pb] += value[pa];//b的根节点成为a的父节点,那么a的权值归入b
}

实例应用:

小苯的蓄水池:https://ac.nowcoder.com/acm/contest/93847/E

题意:

n个蓄水池,从1到n排成一排,第 i i i个蓄水池中的水量为 a i a_i ai

相邻蓄水池有一个隔板,拿开隔板两个蓄水池的水合并,现在有两个操作:

  • 1 将 l , r l, r l,r之间的所有隔板取出,使得这些水池合并
  • 2 查询第 i i i个水池的水量,即当前合并水池的总水量 / 合并的水池数

思路:

  • easy:

    • 使用并查集来维护每个水池,并记录当前集合中点的个数(即集合的权值),以及当前集合水池的总水量

    • 对于l到r的水池,可以以l水池为基准,后续水池若与l水池的根节点不同,则进行合并操作

    • 此时的时间复杂度为O(mn),我们可以通过区间维护来进行优化

  • hard:

    • 将每个水池看做一个存在作用区间的集合,初始状态每个水池的左右边界均为本身
    • 我们在进行合并操作时,不再遍历l到r的水池,这样会重复遍历,从而浪费时间,可以选择l水池的右边界到r水池的左区间进行遍历
    • 每一次合并操作,对当前集合的区间进行拓展,不断压缩需要遍历的区间,从而大大减小时间复杂度。

注意:

  • 不能在每次取出隔板后去修改原水池的数值,会有精度损失
  • 会出现重复取出隔板的情况(隔板取走后便一直为取出状态)

AC code:

#include<bits/stdc++.h>
#define endl '\n'
#define fast() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5+10, M = 2001;
const int INF = 0x3f3f3f3f, MOD = 1e9+7;
int a[N], f[N];struct val{int cnt;double sum;int L, R;
}va[N];int find(int x) {if (f[x] != x) f[x] = find(f[x]); return f[x];
}void solve() {   int n, m; scanf("%d %d", &n, &m);for (int i = 1; i <= n; i ++) {scanf("%d", &a[i]);f[i] = i;va[i].cnt = 1, va[i].sum = a[i];va[i].L = i, va[i].R = i;}while (m --) {int op; scanf("%d", &op);if (op == 1) {int l, r; scanf("%d %d", &l, &r);for (int i = va[f[l]].R + 1; i <= va[f[r]].L; i ++) {int fa = find(i), fb = find(l);if (fa == fb) continue;f[fb] = fa;va[fa].cnt += va[fb].cnt, va[fa].sum += va[fb].sum;va[f[l]].R = max(va[f[l]].R, va[f[i]].R);va[f[l]].L = min(va[f[l]].L, va[f[i]].L);}} else {int pos; scanf("%d", &pos);pos = find(pos);double ans = va[pos].sum / va[pos].cnt;printf("%.9lf\n", ans);}}
} int main() {fast();int T = 1;//cin >> T;while (T --) {solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/466308.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于 Encoder-only 架构的大语言模型

基于 Encoder-only 架构的大语言模型 Encoder-only 架构 Encoder-only 架构凭借着其独特的双向编码模型在自然语言处理任务中表现出色&#xff0c;尤其是在各类需要深入理解输入文本的任务中。 核心特点&#xff1a;双向编码模型&#xff0c;能够捕捉全面的上下文信息。 En…

sql数据库-DQL-条件查询

条件查询 SELECT 字段列表 FROM 表名 WHERE 条件列表; 条件列表 比较运算符功能> 大于>大于等于 < 小于<小于等于等于!不等于between...and...某个范围之间&#xff08;闭区间&#xff09;IN(...)在in之后的列表中的值&#xff0c;多选一LIKE 通…

Android CCodec Codec2 (二十)C2Buffer与Codec2Buffer

在阅读Codec2框架代码时&#xff0c;我们可能会发现好几个名称中都带有“buffer”的类&#xff0c;如MediaCodecBuffer、ABuffer、CCodecBuffers、Codec2Buffer以及C2Buffer。它们分别是什么&#xff1f;各自承担着什么功能&#xff1f;它们之间有何联系&#xff1f;本文将围绕…

WPF怎么通过RestSharp向后端发请求

1.下载RestSharpNuGet包 2.请求类和响应类 public class ApiRequest {/// <summary>/// 请求地址/// </summary>public string Route { get; set; }/// <summary>/// 请求方式/// </summary>public Method Method { get; set; }/// <summary>//…

SQL Server 日志记录

SQL Server是一个关系数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;旨在有效地存储、组织、检索和操作大量结构化数据。SQL Server日志是监控数据库活动、排查问题和确保数据一致性的基础&#xff0c;这些日志记录了SQL Server实例中发生的事件的时间顺序。它们充当…

书生实战营第四期-基础岛第三关-浦语提示词工程实践

一、基础任务 任务要求&#xff1a;利用对提示词的精确设计&#xff0c;引导语言模型正确回答出“strawberry”中有几个字母“r”。 1.提示词设计 你是字符计数专家&#xff0c;能够准确回答关于文本中特定字符数量的问题。 - 技能&#xff1a; - &#x1f4ca; 分析文本&…

默认 iOS 设置使已锁定的 iPhone 容易受到攻击

苹果威胁研究的八个要点 苹果手机间谍软件问题日益严重 了解 Apple 苹果的设备和服务器基础模型发布 尽管人们普遍认为锁定的 iPhone 是安全的&#xff0c;但 iOS 中的默认设置可能会让用户面临严重的隐私和安全风险。 安全研究员 Lambros 通过Pen Test Partners透露&#…

双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动(3)

前言&#xff1a;本篇来到双指针算法介绍的最终篇&#xff0c;该文将通过三个同类型但难度逐渐累增的题目&#xff0c;再次强化对双指针算法的理解和运用。 相关题目及讲解 一. 两数之和 题目链接&#xff1a;LCR 179. 查找总价格为目标值的两个商品 - 力扣&#xff08;LeetC…

sparkSQL的UDF,最常用的regeister方式自定义函数和udf注册方式定义UDF函数 (详细讲解)

- UDF&#xff1a;一对一的函数【User Defined Functions】 - substr、split、concat、instr、length、from_unixtime - UDAF&#xff1a;多对一的函数【User Defined Aggregation Functions】 聚合函数 - count、sum、max、min、avg、collect_set/list - UDTF&#xff1a;…

Springcloud高校选课管理系统-计算机毕业设计源码27115

摘 要 随着信息技术的快速发展和高校信息化建设的深入推进&#xff0c;选课管理系统作为高校教育信息化建设的重要组成部分&#xff0c;其重要性和紧迫性日益凸显。传统的选课管理系统往往采用单体架构&#xff0c;存在系统耦合度高、可维护性差、扩展性不强等问题&#xff0c;…

ChatGPT 新体验:AI 搜索功能与订阅支付指南

就在凌晨&#xff0c;在 ChatGPT 迎来两周岁生日之际&#xff0c;OpenAI 重磅发布了 ChatGPT 的全新人工智能搜索体验。 期待已久的时刻终于到来&#xff0c; ChatGPT 正式转型成为一款革命性的 AI 搜索引擎&#xff01; 先来看看 ChatGPT 搜索&#xff1a;这次不是简单的加个…

奇瑞汽车:降阶模型在新能源汽车热管理仿真上的应用

随着新能源汽车的发展&#xff0c;对仿真技术的要求也越来越高。那么奇瑞汽车利用降阶模型在新能源汽车热管理仿真上做了哪些应用呢&#xff1f;本次内容主要从四个方面展开介绍&#xff1a; 1、 奇瑞汽车简介&#xff1b; 2、 热管理降阶模型开发的背景&#xff1b; 3、 高低…

RPC核心实现原理

目录 一、基本原理 二、详细步骤 三、额外考虑因素 RPC&#xff08;Remote Procedure Call&#xff0c;远程过程调用&#xff09;是一种计算机通信协议&#xff0c;也是一种用于实现分布式系统中不同节点之间进行通信和调用的技术。其实现原理主要可以分为以下几个步骤&…

HTML前端页面设计静态网站-仿百度

浅浅分享一下前端作业&#xff0c;大佬轻喷~ <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>百度&#xff08;伪&#xff09;</title><style>body {margin: 0;padding: 0;}.top-bar {dis…

Linux多线程(个人笔记)

Linux多线程 1.Linux线程概念1.1线程的优点1.2线程的缺点 2.Linux线程VS进程3.Linux线程控制3.1创建线程3.2线程tid及进程地址空间布局3.3线程终止3.4线程等待 4.分离线程5.线程互斥5.1互斥锁mutex5.2互斥锁接口5.3互斥锁实现原理5.4可重入VS线程安全 6.线程同步6.1条件变量6.2…

【MacOS实操】如何基于SSH连接远程linux服务器

MacOS上远程连接linux服务器&#xff0c;可以使用ssh命令pem秘钥文件连接。 一、准备pem秘钥文件 如果已经有pem文件&#xff0c;则跳过这一步。如果手上有ppk文件&#xff0c;那么需要先转换为pem文件。 macOS 的默认 SSH 客户端不支持 PPK 格式&#xff0c;你需要将 PPK 文…

基于CNN-LSTM的时间序列数据预测,15个输入1个输出,可以更改数据集,MATLAB代码

1. 数据收集与预处理 数据清洗&#xff1a;处理缺失值、异常值等。特征工程&#xff1a;提取有助于预测的特征。数据标准化&#xff1a;将时间序列数据标准化&#xff0c;使其具有零均值和单位方差&#xff0c;有助于模型训练。滑动窗口划分&#xff1a;将时间序列数据划分为多…

win 查看显卡支持 CUDA版本

在cmd 中执行 nvidia-smi 二、nvcc -V

Java算法OJ(6)归并分治

目录 1.前言 2.正文 2.1归并分治的概念 2.2计算数组的小和 2.2.1题目 2.2.2示例 2.2.3代码 2.3翻转对 2.3.1题目 2.3.2示例 2.3.3代码 3.小结 1.前言 哈喽大家好吖&#xff0c;今天继续来给大家带来Java算法——归并分治的讲解&#xff0c;学习这篇的前提可以先把…

QML项目实战:自定义Combox

目录 一.添加模块 import QtQuick.Controls 2.4 import QtQuick.Templates 2.4 as T import QtGraphicalEffects 1.15 import QtQuick 2.15 as T2 二.自定义Combox 1.combox文字显示 2.设置下拉图标显示 3.下拉框中选中背景设置 4.下拉框中选中文字设置 5.下拉框设置…