首页 > 代码库 > Building Block[HDU2818]
Building Block[HDU2818]
Building Block
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5426 Accepted Submission(s): 1663
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
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1
0
2
路径压缩的并查集。对每个点x，rank[x]记录到父亲的距离,size[x]表示以x为根节点的子树大小。x下边的积木数=x的最高级父亲father的size-Σ(从x到father的路径上各点的rank)。路径压缩这里写的有点意识模糊，居然一遍AC，提交完自己都挺奇怪，这就过了啊......
#include <stdio.h>#include <string.h>int tmpx;int size[30005], rank[30005];class Union_Find_Set {#define MAX_UNION_FIND_SET_SIZE 30005public: int setSize; int father[MAX_UNION_FIND_SET_SIZE]; Union_Find_Set() { setSize = 0; } Union_Find_Set(int x) { setSize = x; clear(x); } void clear(int x) { for (int i = 0; i < x; i++) { father[i] = i; } } int getFather(int x) { tmpx = 0; int ret = x, tmp; while (ret != father[ret]) { tmpx += (rank[ret]); ret = father[ret]; } int tmpz = tmpx; while (x != father[x]) { tmp = father[x]; father[x] = ret; tmpz -= rank[x]; rank[x] += tmpz; x = tmp; } return ret; } bool merge(int a, int b) { a = getFather(a); b = getFather(b); if (a != b) { father[b] = a; rank[b] = size[a] + 1; size[a] += (size[b] + 1); return true; } else { return false; } } int countRoot() { int ret = 0; for (int i = 0; i < setSize; i++) { if (father[i] = i) { ret++; } } return ret; }};Union_Find_Set ufs;int main() { int n, a, b; char q; while (scanf("%d", &n) != EOF) { memset(size, 0, sizeof(size)); memset(rank, 0, sizeof(rank)); ufs.clear(30001); while (n--) { getchar(); scanf("%c", &q); if (q == ‘M‘) { scanf("%d%d", &a, &b); ufs.merge(a, b); } else if (q == ‘C‘) { scanf("%d", &a); printf("%d\n", size[ufs.getFather(a)] - tmpx); } } } return 0;}
Building Block[HDU2818]