并查集

普通并查集

int get_father(int x){
    if(father[x]==x)return x;
    else return get_father(father[x]);
}
// return father[x]==x ? x : get_father(father[x]);

void merge(int x,int y){
    int fx=get_father(x);
    int fy=get_father(y);
        if(fx==fy)return;
    father[fx]=fy;
    return;
}

路径压缩

int get_father(int x){
    if(father[x]==x)return x;
    else{
        father[x]=get_father(father[x]); // 路径压缩
        return father[x];
    }
    // return father[x]==x ? x : father[x]=get_father(father[x]);
}

启发式合并

以点数为估价函数

int heu_merge(int x,int y){
    int fx=get_father(x);
    int fy=get_father(y);
    if(fx==fy)return;
    if(size[x]<size[y]){
        father[fx]=fy; // 点数小的合并到点数大的上
        size[y]+=size[x]; // 更新点数
    }
    else{
        father[fy]=fx;
        size[y]+=size[x];
    }
    return;
}

以深度为估价函数

int heu_merge(int x,int y){
    int fx=get_father(x);
    int fy=get_father(y);
        if(fx==fy)return;
    if(h[x]>h[y])father[fy]=fx;
    else{
        father[fx]=fy;
        h[y]++;  
    }
    return;
}

扩展域并查集

带权并查集

可持久化并查集

评论