[树]并查集

注意

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

使用方法

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

模板

初始化

const int maxn=2005+5;
int bin[maxn];//bin表示集合树
int sz[maxn];//sz表示每个节点所形成的分支的大小
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];
    }
}