带权并查集

傷城~ 2021-10-13 01:25 315阅读 0赞

### 带权并查集 ###

*  hdu2818 Building Block
 *   *  题意
     *  源代码

# hdu2818 Building Block #

## 题意 ##

初始的时候，给定n堆，每一堆有一块砖，并且编号从1到n
     给定两种操作方式
     (1）M x y 将含有编号为x的一堆砖放置在含有编号为y的那堆砖的上面，如果x,y在同一堆，
     则忽略此操作
     (2) C x  计算编号为x的砖下面含有砖的个数

## 源代码 ##

#include<cstdio>
    const int maxn = 3e4+3;
    int pre[maxn];//并查集中节点指向的前一节点
    int under[maxn];//编号为x下面砖的个数
    int sum[maxn];//当x为底的时候所一堆包含的总数目
    
    /* * 由于是计算一块砖下面所包含砖的个数，为了查找，并且在查找的过程中计算under * 将堆的根节点指向堆底 故有 under[x]+=under[pre[x]]; * 并且查询节点x的时候，将该路径上的节点全都指向根节点 */
    
    /* *初始化 * pre[i]=i;//自己指向自己，相当于每个节点是一颗树，根节点是本身 * sum[i]=1;//初始时，每一堆只包含一个 *under[i]=0;//每一个砖下面没有砖 */
    
    void init(){ 
        for(int i=0;i<maxn;++i)pre[i]=i,sum[i]=1,under[i]=0;
    }//初始化
    
    
    int find(int x)
    { 
        if(x!=pre[x])//x不是根节点
        { 
            int t=find(pre[x]);
            under[x]+=under[pre[x]];
            return pre[x]=t;//路径压缩，使的一堆的节点指向根节点，优化下次查询效率 
        }
        return x;
    }// 查找
    
    void Union(int x,int y)
    { 
        x=find(x),y=find(y);
        if(x!=y)
        { 
            under[x]=sum[y];//x堆放到y堆上，x为堆底
            sum[y]+=sum[x];//砖数相加
            pre[x]=y;//将根节点指向堆底
        }
    }//合并两堆
    
    
    int main(){ 
        int p,x,y;
        char op[2];//%c ,getchar(),不会忽略空白字符
        while (~scanf("%d",&p))
        { 
            init();
           for(int i=0;i<p;++i){ 
                scanf("%s %d",op,&x);
                if(op[0]=='M'){ 
                    scanf("%d",&y);
                    Union(x,y);
                }else { 
                    find(x);//查找时更新under[x],union()操作后并为更新under
                    printf("%d\n",under[x]);
                }
           }
          
        }
        
    }