ACM习题集

并查集

课本上的并查集是很聪明的,find 效率在搜索一次之后会变的很高。从这一点其实可以看出为什么叫集,而不是叫树了,理性状态下,并查集的深度为 1,是最好的。

这会不会和有些电脑系统的搜索方式有关呢?第一次慢些,之后就非常的快?

在合并时,由 rank 值决定由哪个集合来吞并另外一个集合。

 

发表评论

电子邮件地址不会被公开。