并查集

说明

并查集

使用方法

  • init(n);初始化 n为并查集的元素数量
  • findX(x);找到x的根节点
  • merge(a, b);合并a, b所在集合
  • zip1(x);zip2(x);压缩x路径上的所有节点

Tips

  • 该merge为按秩合并,不需要时可以直接使用简化版本
  • 压缩路径使用zip2()较好,递归调用较消耗时间

模版

const int maxn=2005+5;
int bin[maxn];//bin表示集合树
int sz[maxn];//sz表示每个节点所形成的分支的大小

//初始化bin数组
void init(int size){
    for (int i=0; i<=size; i++){
        bin[i]=i;
        sz[i]=1;
    }
}

//找到x的根节点
int findX(int x){
    int r=x;
    while (bin[r]!=r) {
        r=bin[r];
    }
    return r;
}

//路经压缩——递归形式(效率低)
int zip1(int x){
    if (x!=bin[x]) {
        bin[x]=zip1(bin[x]);
    }
    return bin[x];
}

//路经压缩——迭代形式(效率高)
int zip2(int x){
    int tmp, _x = x;
    while ( bin[_x]!=_x )
        _x = bin[_x];
    while ( bin[x]!=x ){
        tmp = bin[x];
        bin[x] = _x;
        x = tmp;
    }
    return _x;
}


//合并两个集合
void merge(int a,int b){
    int aRoot=findX(a);
    int bRoot=findX(b);
    if (aRoot==bRoot) return;
    bin[aRoot]=bRoot
    //这个选择结构只是为了让树更加平衡,即把小树作为大树的子树
    //如果不考虑树的平衡问题,只需使bin[aRoot]=bRoot即可
    if (sz[aRoot] < sz[aRoot]) {
        bin[aRoot] = bRoot;
        sz[bRoot] += sz[aRoot];
    }
    else {
        bin[bRoot] = aRoot;
        sz[aRoot] += sz[bRoot];
    }
}

results matching ""

    No results matching ""