2 月 7 日算法练习- 数据结构-并查集

并查集

并查集是一种图形数据结构,用于存储图中结点的连通关系。
每个结点有一个父亲,可以理解为“一只伸出去的手”,会指向另外一个点,初始时指向自己。
一个点的根节点是该点的父亲的父亲的的父亲,直到某个点的父亲是自己 根
当两个点的根相同时,我们就说他们是属于同一类,或者说是连通的。
如下:7、5、1、3、6的根都是3,所以他们是连通的,2、4是连通的,而2、6不连通,因为他们的根不 同
在这里插入图片描述

找根

找根的方法是:
如果当前点不是根,就返回父亲的根。否则就是自己。
用递归的方法实现

int root(int x){
	if(pre[x]==x)return x;
	return root(pre[x]);
}

合并

在并查集中,所有的操作都在根上,假如我要使得x和y两个点合并,只需要将root(x)指向 root(y),或使得root(y)指向root(x)。 pre[root(x)]= root(y);
例如我要合并4和6.则需要将2指向3或将3指向2.
在这里插入图片描述

路径压缩

找根函数的复杂度最坏情况下会达到O(n),如果查询次数较多的话效率将会非常低下。
我们可以在找根的过程中,将父亲直接指向根,从而实现路径压缩,这样可以使得找根的总体时间复杂度接近O(1)。如下图,执行一次root(7)之后,沿途的点都会直接指向根3。

int root(int x){
	return pre[x] = (pre[x]==x?x:root(pre[x]));
}

在这里插入图片描述

在这里插入图片描述

蓝桥幼儿园

在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 2e5+9;
int pre[N],n,m;

int root(int x){
    pre[x] = (pre[x]==x)?x:root(pre[x]);
    return pre[x];
}

int main( ){
    cin>>n>>m;
    for(int i=1;i<=n;i++)pre[i]=i;
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            pre[root(x)]=root(y);
        }else{
            if(root(x)==root(y))cout<<"YES"<<'\n';
            else cout<<"NO"<<'\n';
        }
    }
    return 0;
}

修改数组

在这里插入图片描述

思路:并查集的查询修改特性,根是未重复的数,非根是重复的数。初始化并查集 pre[i]=i表示每个根都未重复,遍历数组 a,遍历到 x 时将 x 修改为root(x) 的根,将 root(x) 指向 root(x+1) 的根,表示 x 的过去根已经重复,新根未重复。

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N],pre[N];

int root(int x){
    return pre[x] = (pre[x]==x)?x:root(pre[x]);
}

int main( ){
    int n;cin>>n;
    for(int i=1;i<=N;i++)pre[i]=i;
    
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i] = root(a[i]);
        pre[a[i]] = root(a[i]+1);
    }
    
    for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[n==i];
    return 0;
}

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

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

相关文章

【buuctf--来首歌吧】

用 Audacity 打开&#xff0c;左声道部分可以放大&#xff0c;可以按照长短转换成摩斯密码&#xff0c;放大后&#xff1a; ..... -... -.-. ----. ..--- ..... -.... ....- ----. -.-. -... ----- .---- ---.. ---.. ..-. ..... ..--- . -.... .---- --... -.. --... ----- -…

2024 年改变行业的人工智能主要趋势

1、导读 当我们迈入 2024 年时&#xff0c;了解人工智能趋势至关重要。它们不仅仅涉及技术进步&#xff1b;还涉及技术进步。它们意味着我们解决问题、做出决策和展望未来的方式发生了转变。本文旨在探索这些变革趋势&#xff0c;并强调人工智能如何不断突破可能性的界限&…

C++进阶(十二)lambda可变参数包装器

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、新的类功能1、默认成员函数2、类成员变量初始化3、 强制生成默认函数的关键字default:4、…

【软件设计师笔记】深入探究操作系统

【软件设计师笔记】计算机系统基础知识考点(传送门) &#x1f496; 【软件设计师笔记】程序语言设计考点(传送门) &#x1f496; &#x1f413; 操作系统的作用 1.通过资源管理提高计算机系统的效率 2.改善人机界面向用户提供友好的工作环境 &#x1f413; 操作系统的特征 …

leetcode(滑动窗口)483.找到字符中所有字母异位词(C++详细解释)DAY4

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串&#xff08;包括相同的字符串&a…

03-抓包_封包_协议_APP_小程序_PC应用_WEB应用

抓包_封包_协议_APP_小程序_PC应用_WEB应用 一、参考工具二、演示案例&#xff1a;2.1、WEB应用站点操作数据抓包-浏览器审查查看元素网络监听2.2、APP&小程序&PC抓包HTTP/S数据-Charles&Fiddler&Burpsuite2.3、程序进程&网络接口&其他协议抓包-WireSh…

three.js 向量方向(归一化.normalize)

效果&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs" style"border: 1px solid red"></div><div><p><el-button type"primary…

c#: 表达式树的简化

环境&#xff1a; .net 6 一、问题&#xff1f; 有下面的表达式&#xff1a; var nums new List<int> { 1, 2, 3 }; Expression<Func<int, bool>> exp i > i > nums.Max();我们知道&#xff0c;它其实就是&#xff1a;exp i > i > 3; 那么…

史上最全嵌入式(学习路线、应用开发、驱动开发、推荐书籍、软硬件基础)

废话不多说直接上思维导图&#xff01; 如果有觉得图片看不清楚的&#xff0c;有疑问的&#xff0c;可在评论区进行留言&#xff01; 群号&#xff1a; 228447240 嵌入式总括 嵌入式书籍推荐 嵌入式软件知识 嵌入式硬件知识 嵌入式应用开发 嵌入式驱动开发 嵌入式视频推荐: 韦…

5秒搭建PalWorld幻兽帕鲁游戏服务器,你信吗?

5秒搭建PalWorld幻兽帕鲁游戏服务器&#xff0c;你信吗&#xff1f;腾讯云推出幻兽帕鲁专属镜像系统&#xff0c;直接选择镜像&#xff0c;5秒搞定&#xff0c;全自动化部署。 幻兽帕鲁太火了&#xff0c;官方palworld服务器不稳定&#xff1f;不如自建服务器&#xff0c;基于…

双归同一运营商的 BGP 部署

一、拓朴如下&#xff1a; 要求&#xff1a; 1、AS100 只接收 AS200 和 300 的路由&#xff0c;不接收其它 AS 的明细路由&#xff1b; 2、对于 AS100 的业务流量出方向&#xff0c;所有到 AS200 和 300 的流量&#xff0c;优先选择 Line-1&#xff0c;而到 AS400 的流…

SpringBoot Security安全认证框架初始化流程认证流程之源码分析

SpringBoot Security安全认证框架初始化流程&认证流程之源码分析 以RuoYi-Vue前后端分离版本为例分析SpringBoot Security安全认证框架初始化流程&认证流程的源码分析 目录 SpringBoot Security安全认证框架初始化流程&认证流程之源码分析一、SpringBoot Security安…

5.electron之主进程起一个本地服务

如果可以实现记得点赞分享&#xff0c;谢谢老铁&#xff5e; Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 Electron 将 Chromium 和 Node.js 嵌入到了一个二进制文件中&#xff0c;因此它允许你仅需一个代码仓库&#xff0c;就可以撰写支持 Windows、…

基于SpringBoot和PostGIS的震中影响范围可视化实践

目录 前言 一、基础数据 1、地震基础信息 2、全国行政村 二、Java后台服务设计 1、实体类设计 2、Mapper类设计 3、控制器设计 三、前端展示 1、初始化图例 2、震中位置及影响范围标记 3、行政村点查询及标记 总结 前言 地震等自然灾害目前还是依然不能进行准确的预…

基于Springboot的足球社区管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的足球社区管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…

8.0 Zookeeper 四字命令教程详解

zookeeper 支持某些特定的四字命令与其交互&#xff0c;用户获取 zookeeper 服务的当前状态及相关信息&#xff0c;用户在客户端可以通过 telenet 或者 nc&#xff08;netcat&#xff09; 向 zookeeper 提交相应的命令。 安装 nc 命令&#xff1a; $ yum install nc …

[office] Excel 2016怎么绘图?Excel2016绘图图文教程 #媒体#经验分享

Excel 2016怎么绘图&#xff1f;Excel2016绘图图文教程 这篇文章主要为大家介绍了Excel 2016怎么绘图&#xff1f;这篇文章主要介绍了Excel2016绘图图文教程 Excel作为数据处理分析软件&#xff0c;是非常好用的软件。里面可以进行数据统计与分析&#xff0c;如果要使得 Exce…

坚持刷题|二叉树的最近公共祖先

文章目录 题目考察点代码实现实现总结为什么不用迭代的方法实现&#xff1f;二叉搜索树的最近公共祖先 Hello&#xff0c;大家好&#xff0c;我是阿月。坚持刷题&#xff0c;老年痴呆追不上我&#xff0c;今天刷&#xff1a;二叉树的最近公共祖先 题目 236.二叉树的最近公共祖…

JavaWeb后端开发(第一期):Maven基础、Maven的安装配置、如何创建maven项目模块、maven的生命周期

Java后端开发&#xff1a;2024年2月6日 -> LiuJinTao 文章目录 JavaWeb后端开发&#xff08;第一期&#xff09; &#xff1a; maven基础一、 maven介绍1.1 什么maven呢&#xff1a;1.2 maven的作用1.3 maven 模型1.4 maven 仓库 二、maven 安装2.1 配置本地仓库2.2 配置阿里…

设计模式-行为型模式(下)

1.访问者模式 访问者模式在实际开发中使用的非常少,因为它比较难以实现并且应用该模式肯能会导致代码的可读性变差,可维护性变差,在没有特别必要的情况下,不建议使用访问者模式. 访问者模式(Visitor Pattern) 的原始定义是&#xff1a; 允许在运行时将一个或多个操作应用于一…