并查集

[Ir1d]

https://oi-wiki.org/ds/dsu/

[jiangfengyang]

orz

[jtchen2k]

学习了

[sixyang]

orz

[ZiYang-xie]

学习了

[nightrain-vampire]

orz现在就来学

[max-qaq]

orz在爬了在爬了

[LibraFFly]

在 Tarjan 的论文[1]中，证明了不使用启发式合并、只使用路径压缩的最坏时间复杂度是mlogn，这句话确定没有问题嘛，复杂度是对的吗

[CoelacanthusHex]

@LibraFFly 您可以去翻看论文原文，原文末尾有一份表格

[CoelacanthusHex]

在 Tarjan 的论文[1]中，证明了不使用启发式合并、只使用路径压缩的最坏时间复杂度是mlogn，这句话确定没有问题嘛，复杂度是对的吗

[gyety]

orz

[jiaoxinnyu]

学习了

[sinkinben]

复杂度的 m 和 n 分别表示什么

[nipirennipi]

orz

[CYZH1307]

arz啥意思啊

[yxr-yolanda]

带权并查集有代码吗？

[evawyf]

orz

[pigeonwu]

有没有大佬补充一点种类并查集的内容啊QAQ

[DanielCorleone2001]

orz

[Tedhjl]

查找能添加非递归的方法吗

[Alafun]

@CoelacanthusHex

在 Tarjan 的论文[1]中，证明了不使用启发式合并、只使用路径压缩的最坏时间复杂度是mlogn，这句话确定没有问题嘛，复杂度是对的吗

其实我有一个和算法没有关系的问题, 就是:

为什么论文的pdf这么模糊呀, 我之前看到一个很早的经典论文也是好模糊的(pdf不是可以保真吗?) 是因为之前的文档都是是扫描版吗(因为网络当时还不发达, 所以没有保存电子档? )?

👆一直以来的困惑

[Draudnaut]

@CoelacanthusHex

在 Tarjan 的论文[1]中，证明了不使用启发式合并、只使用路径压缩的最坏时间复杂度是mlogn，这句话确定没有问题嘛，复杂度是对的吗

其实我有一个和算法没有关系的问题, 就是:

为什么论文的pdf这么模糊呀, 我之前看到一个很早的经典论文也是好模糊的(pdf不是可以保真吗?) 是因为之前的文档都是是扫描版吗(因为网络当时还不发达, 所以没有保存电子档? )?

👆一直以来的困惑

这篇文章发表的时候还没有pdf，这个应该是后期扫描存档的版本。

[CoelacanthusHex]

其实我有一个和算法没有关系的问题, 就是:

为什么论文的pdf这么模糊呀, 我之前看到一个很早的经典论文也是好模糊的(pdf不是可以保真吗?) 是因为之前的文档都是是扫描版吗(因为网络当时还不发达, 所以没有保存电子档? )?

👆一直以来的困惑

这篇文章发表的时候还没有pdf，这个应该是后期扫描存档的版本。

而且那个时候 PostScript 也才刚刚出现，还是自带点阵字体接受文本的点阵打印机时代，也不存在可以转换到 PDF 的格式，这篇论文应该是手工排印的

[DaYangtuo247]

为什么现在少了这么多内容，之前不是还有并查集的作用和描述的吗

[laosong-2f]

文中提到的姚期智大佬的这篇论文，我发现需要收费，在超星里进行了文献互助，但是还没有收到。

哪位小伙伴有这篇论文？或者哪位小伙伴知道这篇论文的证明过程，可以讲一下。非常感谢。

[jtchen2k]

https://sci-hub.wf/10.1137/0214010