并查集的启发式合并_并查集启发式合并-程序员宅基地

直接实现的话，时间复杂度最坏可以到O(n)。
两个常见优化，启发式合并，路径压缩。
启发式合并：把大小较小的集合挂在较大的集合上。（有的写法是考虑深度而不是大小）
路径压缩：询问过的点到根节点的路径，都直接挂在根节点上。
实现其中任意一个时间复杂度变为O(logn)。
实现其中两个，时间复杂度变为O(α(n))，其中α(n)是阿克曼函数的反函数，可以认为非常小。

多数情况下为了简单，都实现路径压缩（只需要一句赋值）而不实现启发式合并（需要记录深度）。

在某些题目中由于会爆栈，需要使用非递归的find函数。

启发式合并的时间复杂度证明，请参考文献：

doi:10.1145/73007.73040
S2CID 13470414

const int N = 1e4 + 10;
int p[N], rk[N];  //rk是以i为根节点的集合的深度
int n, m;

void init()
{
    
	for(int i = 1; i <= n; i ++)
		p[i] = i, rk[i] = 0;
}

int find(int x)          //路径压缩，非递归式
{
    
	int son = x, tem;
	while(p[x] != x) x = p[x];
	while(son != x)
	{
    
		tem = p[son];
		p[son] = x;
		son = tem;
	}
	return x;
}

void unit(int r1, int r2)   
{
    
	if(rk[r1] > rk[r2])    //启发式合并
		p[r2] = r1;
	else if(rk[r1] < rk[r2])
		p[r1] = r2;
	else              //如果深度相等
	{
    
		p[r1] = r2;
		rk[r2] ++;
	}
}

本文链接：https://blog.csdn.net/weixin_45925735/article/details/112315241

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Android版哆啦A梦连连看游戏源码完整版-程序员宅基地

文章浏览阅读60次。2019独角兽企业重金招聘Python工程师标准>>> ..._哆啦a梦连连看1.6下载

文章浏览阅读2.9k次。流程图，可以说是日常办公中比较常见的一种图表了，开会，有会议流程；采购，有采购流程；财务付款，有付款流程；工作，也有工作流程，可以说它是无处不在。对于普通上班族、白领来说，Office的三个标配Word、Excel、PPT是最常用的工具，但是它却不是最佳的绘制流程图的软件！使用Word、PPT画流程图总是千篇一律，没有特色，如果才能设计出精美、又独具特色的流程图呢?亿图图示设..._word流程图插件

【成功解决】ValueError: `validation_steps=None` is only valid for a generator based on the `keras.utils.Se-程序员宅基地

文章浏览阅读3.3k次。在调试keras的时候，加入验证集，且用生成器来表示的验证集，如下代码history = model.fit_generator(train_gene, validation_data=val_gene, steps_per_epoch=75,epochs=epoch,verbose=1,callbacks=[model_checkpoint])报出如下错误：ValueError: `validation_steps=None` is only valid for a generator b_valueerror: `validation_steps=none` is only valid for a generator based on t

斯伦贝谢宣布2021年第二季度业绩_斯伦贝谢2021产收入-程序员宅基地

文章浏览阅读414次。全球营收56亿美元，环比增长8% 国际营收45亿美元，北美营收11亿美元每股收益0.30美元，环比增长43% 来自于运营的现金流为12亿美元，自由现金流为8.69亿美元董事会批准了0.125美元/股的季度现金派息巴黎--(美国商业资讯)--斯伦贝谢(Schlumberger Limited, NYSE: SLB)今日公布了2021年第二季度业绩。第二季度业绩（单位为百万，每股数额除外) _斯伦贝谢2021产收入

GoLang音视频转码_go 图片视频转码-程序员宅基地

文章浏览阅读3.5k次。一、搭建好开发环境这一步不会的可以百度参考一下这个教程https://www.runoob.com/go/go-environment.html安装ide ，我用的是goland, 个人感觉比较好用支持的平台Linux OS X Windows二、下载第三方工具包go get github.com/xfrr/goffmpeg三、音频转码程序可以直接运行。并且同时支持音频和视频的播放提供的例子是将m4a转码成mp3格式。如果想转换其他格式，只需要修改文件后缀名._go 图片视频转码

MPC5744P-eTimer模块-程序员宅基地

文章浏览阅读4.5k次，点赞9次，收藏32次。1.通道结构5744每个eTimer模块含有6个相同的计数通道，每个计数通道含有16位计数器、分频器、保持寄存器各一个，捕捉寄存器、比较寄存器、比较预加载寄存器各两个，还有四个控制寄存器，其通道结构如下图：2、计数模式、eTimer模块含有多种计数模式，可根据实际情况选择合适的计数模式1、计数上升沿；2、计数跳边沿（上升沿和下降沿均计数）；3、当二次输入为高时计数；4、QUADRA..._etimer

随便推点

C语言字符(&串&数组)处理复习笔记_char str2[] = new char[3]{'w','o','r'}-程序员宅基地

文章浏览阅读103次。C语言字符(&串&数组)处理复习笔记几个函数1.putchar(ch):输出一个字符2.getchar():输入一个字符#include<stdio,h>int main(){ char a,b,c; a = getchar(); b = getchar(); c = getchar(); putchar(a); putchar(b); putchar(c); putchar('\n'); return 0;3.puts(str):输出一个字符串_char str2[] = new char[3]{'w','o','r'}

仿射密码解密（Affine Cipher）-程序员宅基地

文章浏览阅读4.9w次，点赞38次，收藏105次。仿射密码是一种表单代换密码，字母表的每个字母相应的值使用一个简单的数学函数对应一个数值，再把对应数值转换成字母。A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 ..._仿射密码

《Java基础入门第2版》--黑马程序员课后答案及其详解第1章 Java开发入门_java基础入门黑马程序员第二版-程序员宅基地

文章浏览阅读3.8w次，点赞116次，收藏425次。文章目录一、填空题二、判断题三、选择题四、简答题五、编程题六、原题及其解析一、填空题1.(1)Java SE(2)Java EE(3)Java ME2.JRE3.javac4.bin5.(1)path(2)classpath二、判断题 1.√ 2.× 3.√ 4.√ 5.×三、选择题 1.ABCD 2.C 3.D 4.B 5.B四、简答题1、面向对象、跨平台性、健壮性、安全性、可移植性、多线程性、动态性等。2、 JRE（Java Runtime Environm._java基础入门黑马程序员第二版