标签为 [并查集] 的文章

关于并查集单用按秩合并的分析

1.按秩合并的操作 相信大家都知道并查集(不相交集合森林),由于路径压缩优化后时间复杂度分析极难,不易理解,本文来讨论下一种易于分析的优化方式:按秩合并。按秩合并的时间复杂度是O(lgn)的,常数很小,虽然不是特别优秀,但在许多情况下也够用了。 按秩合并的方式就是,对于每一个结点x记录下一个秩(x.rank),表示结点x的高度。每次链接的时候将rank值小的结点的父亲指向rank值大的结点,如果两者秩一样,就随便链哪一个。伪代码: link(x,y) if x.rank>y.rank y.parent ......

BZOJ1015 [JSOI2008]星球大战starwar

题目传送门 明天星球大战8就要在中国上映了,然后今天就来做一下这道题(纯属扯淡) 好了,现在来看这道题。 求联通块的个数,想到用并查集来维护。可是,并查集只能完成加边,不能完成删边的。那怎么办?然后发现题目中只有删点,没有加点,而且没有强制在线,所以想到可以离线做,把删点操作倒过来做,就成了加点了,这就可以用并查集维护了。 code #include<stdio.h> #include<cmath> #include<algorithm> #include<cstdlib> #include ......