Peter算法小课堂—并查集

我们先来看太戈编程467题 攀亲戚

题目描述:

最近你发现自己和古代一个皇帝长得很像:都有两个鼻子一个眼睛,你想知道这皇帝是不是你的远方亲戚,你是不是皇亲国戚。目前你能掌握的信息有m条,关于n个人:第i条信息包含两个人的编号ai,bi,表示ai和bi是亲戚。你的编号是0,皇帝的编号是1,最大编号为n-1,请问能否通过信息推理出你和皇帝是不是亲戚? 备注:众所周知,亲戚关系具有传递性。

连通块问题三大杀手:1.DFS 2.BFS 3.并查集

我们先定义一个id[]数组,表示i号节点的老爸(不是祖宗)。那么……想象一下,把样例构建成一幅图,怎么做呢(想象着想象着就睡着了)?哈哈,我们将无向边化作有向边即可,什么意思呢,就是呢,这个,啊这,嗯,差不多。回到题目,我们发现,皇帝有两个鼻子一个眼睛。

从这个变成……

按连接关系写完id[]。 即看到一条,就在图上加一条边。

那如何判断7和8是否连通呢?其实,我们用root()函数表示一个节点的祖宗,判断root(7)==root(8)就行了。

我们人手动加一条边好弄啊,但是计算机不认识啊,咋办嘞。

我们能不能直接7到8连条线呢?那这时我们发现8的老爸有两个耶,id[8]只能存一个。简单来说就是,不能去修改已经有父亲的点的id。那能不能让1认7做它父亲捏?1又没有父亲。可以是可以,但是……你想想找8的祖宗得走多远呢,换句话说,这棵树的深度太高。正确答案是让1认0做它老爸。所以,unite()函数要调用两次root()。

所以说main()函数如下

int main(){
	cin>>m>>n;
	for(ll i=0;i<n;i++) id[i]=i;
	while(m--){
		cin>>x>>y;
		unite(x,y);
	}
	if(root(1)==root(0)) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

 root()和unite()如下

ll root(ll x){
	if(id[x]==x) return x;
	else return root(id[x]);
}
void unite(ll x,ll y){
	ll rx=root(x),ry=root(y);
	id(rx)=ry;
}

此时看到代码的你立马复制黏贴。殊不知,没有AC。为什么呢?原来可以优化。

这叫“路径压缩”。那优化完的代码长什么样呢?

ll root(ll x){
	return id[x]==x?x:id[x]=root(id[x]);
}

 就这一处变化。那有的小彭友说我用BFS、DFS那不香吗?为什么我们用并查集,因为unite()、root()函数时间复杂度为O(1)!总复杂度O(m+n)!总空间复杂度O(n)!

并查集可视化网址:并查集 (Union-Find Disjoint Sets, 简称UFDS) - VisuAlgo

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

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

相关文章

论文翻译: Vision-Language Foundation Models as Effective Robot Imitators

Vision-Language Foundation Models as Effective Robot Imitators 使用视觉-语言基础模型对机器人进行有效的模仿 文章目录 Vision-Language Foundation Models as Effective Robot Imitators使用视觉-语言基础模型对机器人进行有效的模仿ABSTRACT摘要1 INTRODUCTION1 引言2 …

huggingface学习 | 云服务器使用git-lfs下载huggingface上的模型文件

文章目录 一、找到需要下载的huggingface文件二、准备工作&#xff08;一&#xff09;安装git-lfs&#xff08;二&#xff09; 配置git ssh 三、检查ssh连接huggingface是否成功 一、找到需要下载的huggingface文件 huggingface官网链接&#xff1a;https://huggingface.co/ 以…

东北编程语言???

在GitHub闲逛&#xff0c;偶然发现了东北编程语言&#xff1a; 东北编程语言是由Zhanyong Wan创造的&#xff0c;它使用东北方言词汇作为基本关键字。这种编程语言的特点是简单易懂&#xff0c;适合小学文化程度的人学习&#xff0c;并且易于阅读、编写和记忆。它的语法与其他编…

Linux下安装Mysql【CentOS7 】

Linux下安装Mysql 一、Linux下安装Mysql-5.7.41【tar包下载安装】1.1.首先检查是否已经安装过mysql1.2.下载Linux版本的Mysql-5.71.3.解压缩1.4.安装执行 rpm 安装包需要先下载 openssl-devel 插件1.5.安装 Mysql5.7 执行 rpm 安装包1.6.Mysql相关操作命令1.7.查看Mysql-5.7 临…

生物制药行业研究:预计2029年将达到559亿美元

生物制药是指运用微生物学、生物学、医学、生物化学等的研究成果&#xff0c;从生物体、生物组织、细胞、器官、体液等。综合利用微生物学、化学、生物化学、生物技术、药学等科学的原理和方法制造的一类用于预防、治疗和诊断的制品。 生物制药上游行业主要涉及酵母粉、葡萄糖…

【JavaEEj进阶】 Spring实现留言板

文章目录 &#x1f38d;预期结果&#x1f340;前端代码&#x1f384;约定前后端交互接⼝&#x1f6a9;需求分析&#x1f6a9;接⼝定义 &#x1f333;实现服务器端代码&#x1f6a9;lombok &#x1f332;服务器代码实现&#x1f334;运⾏测试 &#x1f38d;预期结果 可以发布并…

Qt 调试系统输出报警声以及添加资源

文章目录 前言一、方法1 使用 Qsound1.添加都文件 直接报错2.解决这个错误 添加 QT multimedia3. 加入代码又遇到新的错误小结 二、第二种方法1.引入库2.添加资源2.1依次点击Qt--->Qt Resource File--->Choose2.2给资源文件起个名字&#xff0c;如&#xff1a;res&#…

【管理篇 / 升级】❀ 13. FortiOS 7.4固件升级新规则 ❀ FortiGate 防火墙

【简介】飞塔防火墙的固件升级一直是所有厂家中最好的。只要有注册官方帐号&#xff0c;有注册设备&#xff0c;并且只要有一台设备在服务期内&#xff0c;即可下载所有型号的所有版本的固件。即使其它设备服务期已过&#xff0c;也可以通过固件文件手动升级&#xff0c;避免防…

QT界面表格加入勾选框和表格更改颜色显示NG和OK

在QTableWidget上添加框选&#xff0c;获取框选状态 添加选项框在表格中 //添加选择框QTableWidgetItem* check0 new QTableWidgetItem();check0->setCheckState(Qt::Checked);ui->tableWidget_TestResult->setItem(0, 0, check0);ui->tableWidget_TestResult->…

linux安装QQ(官方正版)

QQ官网上有支持linux系统的版本&#xff0c;所以去官网直接下载正版就好。 安装步骤&#xff1a; 1.进入官网&#xff1a;https://im.qq.com/linuxqq/index.shtml 2.选择版本&#xff1a;X86版下载dep 如下所示&#xff1a; 3.下载qq安装包&#xff1a; 4.使用命令安装qq s…

读人工智能专业可以考什么证书呢?

由国家工信部权威认证的人工智能证书是跨入人工智能行业的敲门砖&#xff0c;随着人工智能技术的发展越来越成熟&#xff0c;相关的从业人员也会剧增&#xff0c;证书的考取难度也会变高。如果已经从事或者准备从事人工智能行业的人员&#xff0c;对于考证宜早不宜迟&#xff0…

自建服务器如何备案?

随着互联网的普及和发展&#xff0c;越来越多的人开始考虑自建服务器。然而&#xff0c;在中国大陆地区&#xff0c;自建服务器需要进行备案。本文将介绍自建服务器备案的流程、所需材料以及注意事项。 一、备案流程 确定备案地区 根据《中华人民共和国计算机信息网络国际联网…

excel(vab)删除空行

删除第一、二、三列位空的所有行&#xff08;8000)行范围以内 代码如下&#xff1a; Sub Macro1()Dim hang As Integer For hang 8000 To 1 Step -1If Sheet1.Cells(hang, 1) "" And Sheet1.Cells(hang, 2) "" And Sheet1.Cells(hang, 3) "&quo…

软件测试|Docker cp命令详解:在Docker容器和主机之间复制文件/文件夹

&#x1f525; 交流讨论&#xff1a;欢迎加入我们一起学习&#xff01; &#x1f525; 资源分享&#xff1a;耗时200小时精选的「软件测试」资料包 &#x1f525; 教程推荐&#xff1a;火遍全网的《软件测试》教程 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1…

安泰功率信号源设计方法有哪些

在电子系统中&#xff0c;功率信号源是一个关键的组成部分&#xff0c;用于提供稳定、可靠的电能。这篇文章将详细介绍功率信号源的设计方法&#xff0c;包括选择功率源类型、设计电源拓扑结构、提高效率和管理电磁干扰等方面。 1.功率源类型的选择 选择适当的功率源类型是功率…

MySQL下对[库]的操作

目录 创建数据库 创建一个数据库案例&#xff1a; 字符集和校验规则&#xff1a; 默认字符集&#xff1a; 默认校验规则&#xff1a; 查看数据库支持的字符集&#xff1a; 查看数据库支持的字符集校验规则&#xff1a; 校验规则对数据库的影响&#xff1a; 操作数据…

【计算机硬件】3、输入输出技术、总线结构

文章目录 输入输出技术内存与接口地址的编址方法1、 内存与接口地址独立编址方法2、内存与接口地址统一编址方法 计算机和外设间的数据交互方式1、程序控制(查询)方式2、程序中断方式3、DMA方式&#xff08;直接主存存取&#xff09; 总线结构 输入输出技术 内存与接口地址的编…

Ivanti Connect Secure 曝两大零日漏洞,已被大规模利用

威胁情报公司Volexity发现&#xff0c;影响 Ivanti 的 Connect Secure VPN 和 Policy Secure 网络访问控制 (NAC) 设备的两个零日漏洞正在被大规模利用。自1月11日开始&#xff0c;多个威胁组织在大范围攻击中利用CVE-2023-46805身份验证绕过和CVE-2024-21887命令注入漏洞。 V…

二叉树【Java】

文章目录 一、树型结构二、二叉树2.1概念2.2两种特殊的二叉树2.3二叉树的性质2.4二叉树的遍历 三、二叉树的基本操作3.1获取树中节点的个数3.2获取叶子节点的个数3.3获取第K层节点的个数3.4获取二叉树的高度3.5检测值为value的元素是否存在 一、树型结构 树是一种非线性的数据…

界面设计工具有哪些?看看这5个!

即时设计 - 可实时协作的专业 UI 设计工具即时设计是一款支持在线协作的专业级 UI 设计工具&#xff0c;支持 Sketch、Figma、XD 格式导入&#xff0c;海量优质设计资源即拿即用。支持创建交互原型、获取设计标注&#xff0c;为产设研团队提供一站式协同办公体验。https://js.d…