并查集板子

一、code

  1. 初始化

    int fa[N];
    void init(int n){
        for(int i=0;i<n;i++){
            fa[i]=i;
        }
    }
    
  2. 查询

    注:上溯到根父亲节点

    int find(int now){
        if(fa[now]==now){
            return now;
        }else{
            return find(fa[now]);  //注意这里的para是fa[now]
        }
    }
    
  3. 合并

    注:通常在这里可以进行一些扩展,比如选择特定的根节点进行合并

    void merge(int a,int b){
        fa[find(a)]=find(b);
    }
    

二、优化

  1. 路径压缩

    注:其实将整棵树变为根节点和子节点两层

    int find(int now){
        if(now==fa[now]){
            return now;
        }else{
            fa[now]=find(fa[now]);
            return fa[now];
        }
    }
    
  2. 合并优化

    int height[N];
    void merge(int a,int b){
        int faA=find(a),faB=find(b);
        if(height[faA]>height[faB]){
            fa[faB]=faA;
        }else{
            fa[faA]=faB;
            if(height[faA]==height[faB]){
                height[faA]++;  //只在两棵树同高的情况下更新树高
            }
        }
    }
    

    注:代码混个眼熟,没做检验,毕竟实际使用还是需要做修改的

上一篇:数值计算:线性方程组的迭代解法 02 非静态迭代法


下一篇:2.分治算法