并查集

luckydrawbox · 2021-10-09 23:10:50 · 个人记录

普通并查集

变量

• fa[i]：i 的父亲。

函数

• init(n)：初始化 1\sim n。
• get(x)：找到 x 的根源父亲并路径压缩。
• merge(x,y)：将 x 和 y 所在的集合合并。

每次操作的均摊复杂度为 O(α(n))。

struct Merge_Find{
    int fa[N];
    void init(int n){
        for(int i=1;i<=n;i++)
            fa[i]=i;
    }
    int get(int x){
        return x^fa[x]?fa[x]=get(fa[x]):x;
    }
    void merge(int x,int y){
        fa[get(x)]=get(y);
    }
}mfs;

带权并查集

变量

• fa[i]：i 的父亲。
• d[i]：i 到集合的根的路径上的点权和。

另外外面还需要 w[i] 表示 i 的点权。

函数

• init(n)：初始化 1\sim n。
• get(x)：找到 x 的根源父亲并路径压缩。
• merge(x,y)：将 x 和 y 所在的集合合并。

struct Merge_Find{
    int fa[N],d[N];
    void init(int n){
        for(int i=1;i<=n;i++){
            fa[i]=i;
            d[i]=w[i];
        }
    }
    int get(int x){
        if(x==fa[x])
            return x;
        int root=get(fa[x]);
        d[x]+=d[fa[x]]+w[x];
        return fa[x]=root;
    }
    void merge(int x,int y){
        x=get(x);y=get(y);
        fa[x]=y;
        d[x]=d[y]+w[x];
    }
}mfs;