并查集基础学习笔记
2021/9/10 6:05:38
本文主要是介绍并查集基础学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
并查集的定义(百度搜索):
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。
并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。
1.初始化
设立一个数组f,f[i]表示i的大哥,初始化时把i的大哥定为自身.
for(i=1;i<=n;i++)f[i]=i;//初始化
2.查询
找到x最大的大哥,我这里称为老大.
通过递归的方式来查询,如果一个人的大哥是自己,他就是这棵树里的根.
int find(int x){ if(f[x]==x)return x;//递归边界,判断自己是不是老大. return find(f[x]);//通过递归调用,x的大哥的大哥......,直到找到是老大为止. }//找到x的老大
考虑一下当树为一条链的时候,查询的时间复杂度便达到了o(n),考虑优化.
于是便有了路径压缩:
假设有三个人小甲,小乙,小丁.
小甲是小乙的大哥,小乙是小丁的大哥,那么实则小甲就是小丁的老大.
现在不管谁的大哥是谁,只关心谁的老大是谁,那么就可以进行如下优化:
int find(int x){ if(f[x]==x)return x; return f[x]=find(f[x]); /* 也就是: f[x]=find(f[x]); return f[x]; */ }//找到x的老大
此时进行完x的查询后,他以及他的大哥一直到他的老大的f数组都更新为x的老大.也就是把下图的f[5],[4],f[3],f[2],f[1]都改为f[1].f数组此时指向的便是x这条路径上的经过元素的老大了。但此时树只有两层,大哥也就是老大,所以f数组的含义也就是大哥,与原来一样.
优化后树只有两层.
3.合并
没什么好解释的,也就是把x的老大的大哥(f[find(x)])赋值为y的老大,把x的帮派直接合并与y的帮派.f[find[x]]=find(y).
.代码如下:
int a=find(x);//x的老大 int b=find(y);//y的老大 f[a]=b;//把y的老大当成x的老大的大哥 /* 但由于前面路径压缩,不存在大哥(可以理解一棵树包括 根结点一共有2层,第一层是所有人的老大,第 二层的人之间没有大哥和小弟这层关系,他们的老大是共同的且只有一个) */
题目练习:P3367
这篇关于并查集基础学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南