• 周日. 10 月 6th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

再学并查集

admin

11 月 28, 2021

并查集好啊!

虽然并查集很好,但是我对它的掌握却十分肤浅。
搬运算导
1.单用路径压缩复杂度(O(n+m*(1+log_{2+m/n}n)))
证明是不可能有的。
2.单用按秩合并并且记忆化复杂度(O(nlogn+m))
由于路径压缩也是一种记忆化,所以混合策略也有该上界。
复杂度显然。
3.假设所有(link)在所有(find)前,复杂度(O(m)),只使用路径压缩或使用混合策略。势能分析一下。
4.众所周知,(alpha(n)=min { k:A_{k}(1) ge n })
可得上界(O(m alpha(n)))
(alpha^{‘}(n)=min { k:A_{k}(1) ge lg(n+1) })
使用混合策略时,可得到上界(O(m alpha{‘}(n)))
对于(n)的所有实际值,(alpha^{‘}(n) le 3)
证明是不可能有的。
总之,跑得挺快。
贴代码

struct dsu{
    int fa[N];
    void init(int len){
	    memset(fa,-1,sizeof(*fa)*(len+1));
    }
    int find(int x){
    	return fa[x]<0?x:find(fa[x]);
    }
    int unite(int x,int y){
	    x=find(x);
	    y=find(y);
    	if (fa[x]<fa[y]){
    	    fa[x]+=fa[y];
    	    fa[y]=x;
    	}
    	else{
    	    fa[y]+=fa[x];
    	    fa[x]=y;
    	}
    }
};

递归写法好啊!
6.并查集的线性情况,可以优化一堆东西的理论复杂度
http://ljt12138.blog.uoj.ac/blog/4874

发表回复