HDU 2818 Building Block, poj 1988 Cube Stacking：带权并查集

HDU 2818 Building Block, poj 1988 Cube Stacking：带权并查集2014-12-06链接:

HDU: http://acm.hdu.edu.cn/showproblem.php？pid=2818

POJ: http://poj.org/problem？id=1988

题目：

Problem Description

John are playing with blocks. There are N blocks （1 <= N <= 30000） numbered 1...N。Initially, there are N piles, and each pile contains one block. Then John do some operations P times （1 <= P <= 1000000）. There are two kinds of operation:M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command.C X : Count the number of blocks under block X You are request to find out the output for each C operation.

Input

The first line contains integer P. Then P lines follow, each of which contain an operation describe above.

Output

Output the count for each C operations in one line.

Sample Input

6M 1 6C 1M 2 4M 2 6C 3C 4

Sample Output

102

Source

2009 Multi-University Training Contest 1 - Host by TJU

题目大意：

有N个砖头，编号为1～N，然后有两种操作，第一种是M x y, 把x所在的那一堆砖头全部移动放到y所在的那堆的上面。第二种操作是C x，即查询x下面有多少个砖头，并且输出。

分析与总结：

带权并查集的应用，用num数组来表示每一棵树的总数， rank[x]数组来表示x砖头下面有多少个砖头。

如果把a堆砖放到b堆砖上面，那么a堆最底面那个砖头root_a的下面原本是有0个砖头的，搬过去之后，变成了有b堆砖的数量个。然后root_a之上的数量便根据root_a的值进行更新。更新的步骤在查找时路径压缩的那一步进行。

代码：

#include<cstdio>const int N = 30005;int f[N];long long rank[N],num[N];inline void init（）{for（int i=0; i<N; ++i）f[i]=i,rank[i]=0,num[i]=1;}int find（int x）{if（x==f[x]） return f[x];int fa = f[x];f[x] = find（f[x]）;if（rank[fa]！=0）rank[x] += rank[fa];return f[x];}inline void Union（int x,int y）{int a=find（x）, b=find（y）;if（a==b） return ;rank[a] = num[b];f[a] = b;num[b] += num[a];num[a] = 0;}int main（）{int t, x, y;char cmd[3];scanf（"%d",&t）;init（）;for（int i=0; i<t; ++i）{scanf（"%s",cmd）;if（cmd[0]=="M"）{scanf（"%d%d",&x,&y）;Union（x,y）;}else{scanf（"%d",&x）;find（x）;printf（"%lld
", rank[x]）;}}return 0;}

作者：csdn博客 shuangde800