UVA11987 Almost Union-Find 并查集的节点删除

题意：

第一行给出一个n，m,表示 n个集合，里面的元素为1~n，下面有m种操作，第一个数为 1 时，输入a,b 表示a，b 两个集合合并到一起，第一个数为 2 时，输入a，b表示将 a 从他原来的集合中拿出来，放到集合 b 中，第一个数为 3 时，输入a，表示询问a 所在的集合的元素的个数和元素的和。

思路：

求集合所有元素的个数和元素和的时候，在两个数并为一块的时候求比较容易理解，假如a向b靠拢，那么将a 的信息归并到b里面，相当于这个集合的信息在他的根节点上。

删除节点：初始化newid[i]=i,我们用这个数组的下标来表示几号点，里面的值用++n来表示更新，数值++n的信息初始化为下标。

注意： 合并集合的时候注意谁合并到谁。

void move(int v)

{

    int t=getf(newid[v]);

    sum[t]-=v;

    count[t]--;//原来的并查集减去相应的结果

    newid[v]=++n;//找一个新节点代替 v

    sum[n]=v;//它的值还是v 不变

    f[n]=n;//祖先是自己

    count[n]=1;//1个点

}

//以后对集合a的操作用newid[a]来代替a

看完整代码：

#include<stdio.h>

typedef long long ll;

int count[200100],f[200100],newid[200100];

ll sum[200100];

int getf(int v)

{

    if(f[v]==v)

        return v;

    return f[v]=getf(f[v]);

}

void merge(int u,int v)

{

    int t1=getf(newid[u]),t2=getf(newid[v]);//------

    if(t1!=t2)

    {

        f[t2]=t1;

        sum[t1]+=sum[t2];//t2向t1靠拢

        count[t1]+=count[t2];//累加结果

    }

}

int n,m;

void move(int v)

{

    int t=getf(newid[v]);

    sum[t]-=v;

    count[t]--;//原来的并查集减去相应的结果

    newid[v]=++n;//找一个新节点代替 v

    sum[n]=v;//它的值还是v 不变

    f[n]=n;//祖先是自己

    count[n]=1;//点

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        for(int i=0; i<=n; i++)

            count[i]=1,newid[i]=i,f[i]=i,sum[i]=i;

        int a,b,c;

        for(int i=0; i<m; i++)

        {

            scanf("%d",&a);

            if(a==3)

            {

                scanf("%d",&b);

                printf("%d %lld\n",count[getf(newid[b])],sum[getf(newid[b])]);

            }

            else

            {

                scanf("%d%d",&b,&c);

                if(getf(newid[b])==getf(newid[c]))

                    continue;

                if(a==1)

                    merge(b,c);

                else

                {

                    move(b);//删除节点b

                    merge(c,b);//b向c靠拢

                }

            }

        }

    }

    return 0;

}

巴特西

UVA11987 Almost Union-Find 并查集的节点删除

最新文章

热门文章