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[], rank[];

class Union_Find_Set {

#define MAX_UNION_FIND_SET_SIZE 30005

public:

    int setSize;

    int father[MAX_UNION_FIND_SET_SIZE];

    Union_Find_Set() {

        setSize = ;

    }

    Union_Find_Set(int x) {

        setSize = x;

        clear(x);

    }

    void clear(int x) {

        for (int i = ; i < x; i++) {

            father[i] = i;

        }

    }

    int getFather(int x) {

        tmpx = ;

        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] + ;

            size[a] += (size[b] + );

            return true;

        } else {

            return false;

        }

    }

    int countRoot() {

        int ret = ;

        for (int i = ; 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, , sizeof(size));

        memset(rank, , sizeof(rank));

        ufs.clear();

        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 ;

}

巴特西

Building Block[HDU2818]

最新文章

热门文章