并查集（Disjoint Set）

最常见的两种操作

1.合并

2.查找

实现方法



代码实现

findl(int x)
{
    return set[x];
}
merge(int a,int b)
{
    i = min(a,b);
    j = max(a,b);
    for( k = 1 ; k <= n ; k++)
    {
        if(set[k] == j)
        {
            set[k] = i ;
        }
    }
}

合并操作的时间较为复杂

线性操作时间复杂度o（n）

实现方法二

树状结构 ， 也是最常用的方法



find(x)
{
    r = x ;
    while(bin[r] != r)
    {
        r = bin[r];
    }
    return r ;
}
、

压缩路径 ！！！！！！
find(int x)
{
    if( x != bin[x])
        bin[x] = find(bin[x])
    return bin[x];
}

压缩路径之前



压缩路径之后



void merge(int x , int y)
{
    int fx , fy ;
    fx = find(x);
    fy = finx(y);
    if(fx != fy)
        bin[fx] = fy;
}

经典应用最小生成树

Kruskal算法

