九、数据结构(并查集)

文章目录

    • 1.并查集操作的简单实现
    • 2.解决问题
    • 3. 并查集优化
        • 3.1 合并的优化
        • 3.2查询优化
        • 3.3查询优化2

通常用“帮派”的例子来说明并查集的应用背景:在一个城市中有 n ( n < 1 0 6 ) n(n < 10^6) n(n<106)个人,他们分成不同的帮派,给出一些人的关系,例如: 1 1 1号、 2 2 2号是朋友; 1 1 1号、 3 3 3号也是朋友,那么他们都属于一个帮派。在分析完所有的朋友关系之后,问有多少帮派,每人属于哪个帮派。

这个数据量应该是不能用暴力的办法求解,那我们应该怎么办呢?
由此,我们引出一种新的数据结构:并查集

1.并查集操作的简单实现

  1. 初始化:
    定义数组 i n t   s [   ] int\ s[\ ] int s[ ] 是以结点 i i i 为元素的并查集,在开始的时候还没有处理点与点之间的朋友关系,所以每个点属于独立的集,并且以元素 i i i 的值表示它的集 s [ i ] s[ i ] s[i],例如元素 1 1 1的集 s [ 1 ] = 1 s[1]=1 s[1]=1。所示为图解,左边给出了元素与集合的值,右边画出了逻辑关系。为了便于讲解,左边区分了结点 i i i 和集 s s s (把集的编号加上了下画线);右边用圆圈表示集,方块表示元素。
  2. 合并(1):
    例如加入第 1 个朋友关系 ( 1 , 2 ) (1,2) (1,2),如下图所示。在并查集s中,把结点 1 合
    并到结点 2,也就是把结点 1 的集 1 改成结点 2 的集 2 。
  3. 合并(2):
    加入第 2 2 2 个朋友关系 ( 1 , 3 ) (1,3) (1,3),如下图所示。查找结点 1 1 1 的集是 2 2 2 ,再递归查找元素 2 2 2 的集是 2 2 2 ,然后把元素 2 2 2 的集 2 2 2 合并到结点 3 3 3 的集 3 3 3 。此时,结点 1 1 1 2 2 2 3 3 3属于一个集。在图中,为了简化图示,把元素 2 2 2 和集 2 2 2 画在了一起。
  4. 合并(3):
    加入第 3 3 3 个朋友关系 ( 2 , 4 ) (2,4) (2,4), 如图所示。
  5. 查找:
    在上面步骤中已经有查找操作。查找元素的集是一个递归的过程,直到元素的值和它的集相等就找到了根结点的集。从上面的图中可以看到,这棵搜索树的高度可能很大,复杂度是 O ( n ) O_{(n)} O(n)的,变成了一个链表,出现了树的“退化”现象。
  6. 统计有多少个集:
    如果 s [ i ] = i s[ i ] = i s[i]=i,这是一个根结点,是它所在的集的代表。统计根结点的数量,就是集的数量。

2.解决问题

n n n 个人一起吃饭,有些人互相认识。认识的人想坐在一起,不想跟陌生人坐。例如 A A A 认识 B B B B B B 认识 C C C,那么 A A A B B B C C C会坐在一张桌子上。给出认识的人的关系,问需要多少张桌子。

我们可以根据上文的描述,得到如下并查集代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1007;
int f[N];  //并查集

void init(){  //初始化
    for(int i = 1; i <= N; i++){
        f[i] = i;
    }
}

int find_father(int x){  //找自己的集
    if(f[x] == x)return x;
    else return find_father(f[x]);
}

void union_set(int x, int y){  //合并
    x = find_father(x);
    y = find_father(y);
    if(x != y)f[x] = f[y];
}
int main(){
    init();
    int n, m, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> x >> y;
        union_set(x, y);
    }
    int cnt = 0;  //记录集的数量
    for(int i = 1; i <= n; i++){
        if(f[i] == i){
            cnt ++;
        }
    }
    cout << cnt;
    return 0;
}

在上述程序中,查找、合并、的搜索深度是树的长度,复杂度都是 O ( n ) O_{(n)} O(n),性能比较差。下面介绍合并和查找的优化方法,优化之后,查找和合并的复杂度都小于 O ( l o g 2 n ) O(log_2n) O(log2n)

3. 并查集优化

3.1 合并的优化

在合并元素 x x x y y y时先搜到它们的根结点,然后再合并这两个根结点,即把一个根结点的集改成另一个根结点。这两个根结点的高度不同,如果把高度较小的集合并到较大的集上,能减少树的高度。下面是优化后的代码,在初始化时用 h e i g h t [ i ] height[i] height[i] 定义元素 i i i 的高度,在合并时一同更改。

int high[N];
void init(){  //初始化
    for(int i = 1; i <= N; i++){
        f[i] = i;
        high[i] = 0;
    }
}
void union_set(int x, int y){  //优化合并
    x = find_father(x);
    y = find_father(y);
    if(high[x] == high[y]){
        high[x]++;
        f[y] = x;
    }
    else{
        if(high[x] < high[y]){
            f[x] = y;
        }
        else{
            f[y] = x;
        }
    }
}
3.2查询优化

在上面的查询程序 f i n d f a t h e r ( ) find_father() findfather() 中,查询元素 i i i 所属的集需要搜索路径找到根结点,返回
的结果是根结点。这条搜索路径可能很长。如果在返回的时候顺便把 i i i 所属的集改成根结
点,如图所示,那么下次再搜的时候就能在 O ( 1 ) O_{(1)} O(1) 的时间内得到结果。

int find_father(int x){ //优化的查询 
	if(f[x] != x)f[x] = find_father(f[x]);  
	return f[x];  
}

这个方法称为路径压缩,因为在递归过程中,整个搜索路径上的元素(从元素 i i i 到根结点的所有元素)所属的集都被改为根结点。路径压缩不仅优化了下次查询,而且优化了合并,因为在合并时也用到了查询。

3.3查询优化2

上面的代码用递归实现,如果数据规模太大,担心爆栈,可以用下面的非递归代码:

int find_father(int x) {
    int r = x;
    while (f[r] != r)r = f[r];  //找到根的位置
    int i = x, j;
    while(i != r){
        j = f[i];
        f[i] = r;  //把路径的根统一
        i = j;
    }
    return r;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[算法刷题积累] 两数之和以及进阶引用

两数之和很经典&#xff0c;通常对于首先想到的就是暴力的求解&#xff0c;当然这没有问题&#xff0c;但是我们如果想要追求更优秀算法&#xff0c;就需要去实现更加简便的复杂度。 这里就要提到我们的哈希表法: 我们可以使用unordered_map去实现&#xff0c;也可以根据题目&a…

【Linux】线程(二:线程控制)

本篇文章主要围绕线程控制来进行展开。 主题思路是以create与join两个接口展开。 目录 pthread_create 与 pthread_join:pthread_create:pthread_join: 代码&#xff1a;问题一&#xff1a;主线程与新线程谁先退出&#xff1f;问题二&#xff1a;哪个线程应该最后退出&#xf…

【关键点检测和描述】SuperPoint

一、引言 论文&#xff1a; SuperPoint: Self-Supervised Interest Point Detection and Description 作者&#xff1a; Magic Leap 代码&#xff1a; SuperPoint 特点&#xff1a; 提出Homographic Adaptation策略&#xff0c;提升模型从虚拟数据迁移到真实数据的表现&#x…

邻氯苯甲酰氯在医药、农药等领域应用广泛 市场需求稳定且有增长趋势

邻氯苯甲酰氯在医药、农药等领域应用广泛 市场需求稳定且有增长趋势 邻氯苯甲酰氯又称为2-氯苯甲酰氯、氯化邻氯苯甲酰&#xff0c;化学式为C7H4Cl2O&#xff0c;是一种化学物质&#xff0c;外观为黄色液体&#xff0c;不溶于水&#xff0c;溶于醇、醚、丙酮&#xff0c;有强烈…

第100+12步 ChatGPT学习:R实现KNN分类

基于R 4.2.2版本演示 一、写在前面 有不少大佬问做机器学习分类能不能用R语言&#xff0c;不想学Python咯。 答曰&#xff1a;可&#xff01;用GPT或者Kimi转一下就得了呗。 加上最近也没啥内容写了&#xff0c;就帮各位搬运一下吧。 二、R代码实现KNN分类 &#xff08;1&a…

API 设计技巧:基础知识与实践的方法

在这篇深入探讨中&#xff0c;我们将从基础开始&#xff0c;逐步介绍 API 设计&#xff0c;并探讨定义卓越API的最佳实践。 作为一名开发者&#xff0c;你可能已经熟悉了许多这些概念&#xff0c;但我将提供详细解释&#xff0c;以加深你的理解。 API 设计&#xff1a;电子商…

图纸管理最佳实践:从混乱到有序的转变

图纸管理最佳实践&#xff1a;从混乱到有序的转变 在工程项目中&#xff0c;图纸是不可或缺的重要资料&#xff0c;它们承载着设计者的智慧与心血。然而&#xff0c;随着项目的推进和时间的推移&#xff0c;图纸管理往往变得混乱不堪&#xff0c;给项目的顺利进行带来诸多不便。…

ROS(四)

write in advance 实验四&#xff0c;在经历了实验三的失败后&#xff0c;卷土重来。 幸运的是&#xff0c;此次实验很简单&#xff0c;很快就能搞定。 Part one 使用指令查看自己摄像头的设备号&#xff0c;如果报错&#xff0c;且你为虚拟机&#xff0c;可能是未在虚拟机处…

Java学习 (二)关键字、标识符、数组

一、关键字 我们第一章案例中有很多关键字&#xff0c;比如class、public、static、void等&#xff0c;这些关键字依旧被java定义好了&#xff0c;可以拿来用&#xff0c;不需要死记硬背&#xff0c;按照官方文档查询即可 #官方文档 https://docs.oracle.com/javase/tutorial/j…

docker-compose设置永久启动、自动重启

步骤一 找到 docker-compose.yml 文件 步骤二 vim 打开文件 找到 image: PS&#xff1a;就是为了对齐格式 步骤三 在其下方添加&#xff1a; restart: always而后保存即可

打开nginx连接的php页面报错502

目录 问题描述&#xff1a; 原因&#xff1a; 1. 使用 Unix 域套接字&#xff08;Unix Socket&#xff09; 区别和优势&#xff1a; 2. 使用 TCP/IP 套接字 区别和优势&#xff1a; 如何选择 扩展&#xff1a;Rocky_Linux9.4安装PHP的步骤&#xff1a; 使用Remi存储库…

Wifi通信协议:WEP,WPA,WPA2,WPA3,WPS

前言 无线安全性是保护互联网安全的重要因素。连接到安全性低的无线网络可能会带来安全风险&#xff0c;包括数据泄露、账号被盗以及恶意软件的安装。因此&#xff0c;利用合适的Wi-Fi安全措施是非常重要的&#xff0c;了解WEP、WPA、WPA2和WPA3等各种无线加密标准的区别也是至…

通过防抖动代码解决ResizeObserver loop completed with undelivered notifications.

通过防抖动代码解决ResizeObserver loop completed with undelivered notifications. 一、报错内容二、解决方案解释&#xff1a; 一、报错内容 我通过el-tabs下的el-tab-pane切换到el-table出现的报错&#xff0c;大致是渲染宽度出现了问题 二、解决方案 扩展原生的 Resiz…

Android 应用加固与重签名—使用AndroidStudio自带工具 apksigner

由 AndroidStudio 生成的release版本的app有自己的签名&#xff0c;但当应用加固后会删除原签名&#xff0c;需要重新签名。 一、加固方式&#xff1a; 使用基础版的腾讯云&#xff08;乐固&#xff09;进行免费加固&#xff0c;上传软件后等待在线加固完成后下载 apk 即可。…

vue3+ts+vite集成eslint

项目中安装eslint yarn add eslint -Deslint初始化 npx eslint --init按照下方操作即可 安装typescript-eslint/parser yarn add typescript-eslint/parser -D安装vite-plugin-eslint2 yarn add vite-plugin-eslint2 -D配置vite-plugin-eslint2 // vite.config.ts import …

钡铼技术BL104在环境监测站多协议采集保障数据全面准确

随着工业化和城市化进程的加快&#xff0c;环境污染问题日益严重&#xff0c;环境监测站在保护生态环境、保障公众健康中的作用变得越来越重要。钡铼技术PLC物联网关BL104&#xff0c;为环境监测站提供了一种高效、可靠的多协议数据采集解决方案&#xff0c;保障了监测数据的全…

如何实现对文件发送全生命周期的外发管理?

在日常工作中&#xff0c;我们需要经常和企业外部的机构或者个人&#xff0c;发送一些企业内部的文档或者图纸等资料。但企业在文件外发管理上&#xff0c;仍存在一定漏洞&#xff0c;有些员工会通过一些手段&#xff0c;将重要核心文件数据发过去&#xff0c;包括但不仅限于以…

【数据结构(邓俊辉)学习笔记】二叉搜索树02——查找、插入和删除

文章目录 1.概述2. 查找2.1 查找&#xff1a;算法2.2 查找&#xff1a;理解2.3 查找&#xff1a;实现2.4 查找&#xff1a;语义 3. 插入3.1 插入&#xff1a;算法3.2 插入&#xff1a;实现 4. 删除4.1 删除&#xff1a;框架4.2 删除&#xff1a;单分支4.3 删除&#xff1a;双分…

MySQL----redo log重做日志原理及流程

重做日志 redo log&#xff1a;重做日志&#xff0c;用于记录事务操作的变化&#xff0c;确保事务的持久性。redo log是在事务开始后就开始记录&#xff0c;不管事务是否提交都会记录下来&#xff0c;在异常发生时&#xff08;如数据持久化过程中掉电&#xff09;&#xff0c;…

笔记-python里面的xlrd模块详解

那我就一下面积个问题对xlrd模块进行学习一下&#xff1a; 1.什么是xlrd模块&#xff1f; 2.为什么使用xlrd模块&#xff1f; 3.怎样使用xlrd模块&#xff1f; 1.什么是xlrd模块&#xff1f; ♦python操作excel主要用到xlrd和xlwt这两个库&#xff0c;即xlrd是读excel&…