HDU -2818- Building Block 【带权并查集】题解

小鱼儿 2021-07-24 23:23 321阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.题意
         *  3.思路
         *  4.代码

### 1.题目 ###

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**  
6  
M 1 6  
C 1  
M 2 4  
M 2 6  
C 3  
C 4  
**Sample Output**  
1  
0  
2  
**Sponsor**

### 2.题意 ###

有N个箱子，两种操作，M X Y，将含有X箱子的一堆箱子放到Y箱子上，C X ，询问X箱子下有多少箱子。

### 3.思路 ###

**带权并查集**  
建立三个数组。fa\[i\],记录i的父节点。under\[i\],i箱子下的箱子数目。depth\[i\],根节点为i的树的深度。详细解释看代码。

### 4.代码 ###

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn = 3e4 + 10;
    int fa[maxn], under[maxn],depth[maxn];
    void init()     ///初始化
    { 
    	for (int i = 0; i <= maxn; i++) //要从0开始初始化，否则会出错
    	{ 
    		fa[i] = i;    
    		under[i] = 0; //刚开始每个箱子下没有箱子
    		depth[i] = 1; //树的深度为1
    	}
    }
    int find(int x)
    { 
    	if (x != fa[x])
    	{ 
    		int tmp = fa[x];
    		fa[x] = find(fa[x]);    //路径压缩
    		under[x] += under[tmp]; //x箱子下的数目=x到父节点箱子数+x父节点到根节点箱子数
    	}
    	return fa[x];
    }
    void merge(int i, int j)
    { 
    	int x = find(i), y = find(j);
    	if (x != y)
    	{ 
    		fa[x] = y;
    		under[x] = depth[y];  //合并后，x箱子下的数目=根节点为y树的深度
    		depth[y] += depth[x]; //y树的深度增加
    	}
    	return;
    }
    int main()
    { 
    	int T;
    	cin >> T;
    	init();
    	while (T--)
    	{ 
    		char str[3];
    		int a, b;
    		cin >> str;
    		if (str[0] == 'M')
    		{ 
    			cin >> a >> b;
    			merge(a, b);
    		}
    		else
    		{ 
    			cin >> a;
    			find(a);
    			cout << under[a] << endl;
    		}
    	}
    	return 0;
    }