首页 > ACM题库 > HDU-杭电 > HDU 2818-Building Block-并查集-[解题报告]HOJ
2014
02-17

HDU 2818-Building Block-并查集-[解题报告]HOJ

Building Block

问题描述 :

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.

输入:

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

输出:

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

样例输入:

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

样例输出:

1
0
2

点击打开hdu 2818

思路: 带权并查集
分析:
1 题目给定2种指令 M x y把x的集合放在y集合的上面,C x求x的下面有多少个元素
2 我们用rank[x]表示x以下有多少个元素,那么对于指令M x y我们始终把左边的合并到右边,那么这样rank就满足压缩的性质
3 但是因为这边的合并和普通不一样,它是把x所在的集合放在y所在集合上面,实际上是x的跟节点合并到y集合的最远点,所以我们应该开个数组记录当前集合最远的点

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 30010;

int n;
int father[MAXN];
int rank[MAXN];
int maxNum[MAXN];

void init(){
    memset(rank , 0 , sizeof(rank));
    memset(maxNum , 0 , sizeof(maxNum));
    for(int i = 0 ; i < MAXN ; i++)
        father[i] = i;
}

int find(int x){
    if(father[x] != x){
        int fa = father[x];
        father[x] = find(fa);
        rank[x] += rank[fa];
    }
    return father[x];
}

void Union(int x , int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy){
        father[fx] = fy; 
        rank[fx] += maxNum[fy]+1;
        maxNum[fy] += maxNum[fx]+1;
    }
}

int main(){
    char c;
    int x , y;
    while(scanf("%d%*c" , &n) != EOF){
         init(); 
         while(n--){
              c = getchar();      
              if(c == 'M'){
                  scanf("%d%d%*C" , &x , &y);
                  Union(x , y);
              }
              else{
                  scanf("%d%*C" , &x);
                  find(x);
                  printf("%d\n" , rank[x]);
              }
         } 
    }
    return 0;
}

解题参考:http://blog.csdn.net/chenguolinblog/article/details/9900123


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  4. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  5. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。