并查集 按秩优化 探讨

study from:

https://www.zhihu.com/question/35090745

https://blog.csdn.net/CABI_ZGX/article/details/82530925

对于两个树a,b,根节点分别为ra,rb,树的子节点分别为ga,gb

如果ra并到rb,则对于ra的所有点aa,如果之后合并aa与树a外的某一点,

则aa从原来祖先为ra的基础上,再从ra走到ra的祖先,操作次数+1

所以我认为并查集按秩操作时记录子树的节点数更为合理一点。

更为严谨的想法:

对于一棵子树,它的子节点在之后的操作中,与子树外的点进行合并的操作次数,记为g

应该是判断两棵子树的g值更为合理一点。

虽然这真的真的节省不了多少时间,毕竟时间复杂度已经是O(an),a很小。

如果要实测的话,n需要设置很大的规模了。

原文地址:https://www.cnblogs.com/cmyg/p/11187702.html