poj 1988(并查集)

发布时间：2020-12-13 20:42:29 所属栏目：PHP教程来源：网络整理

导读：题意：有30000个木块，编号从1到30000，然后有两种操作M a b，把木块a所在的堆块放到木块b所在的堆块上，操作C a，询问木块a下面有多少个木块。题解：用1个数组s[i]存木块i所在堆块1共有多少个木块，由于要求木块i下面有多少个木块，所以再添加1个数组dis[i

题意：有30000个木块，编号从1到30000，然后有两种操作M a b，把木块a所在的堆块放到木块b所在的堆块上，操作C a，询问木块a下面有多少个木块。
题解：用1个数组s[i]存木块i所在堆块1共有多少个木块，由于要求木块i下面有多少个木块，所以再添加1个数组dis[i]存木块i到根节点有多少个木块，这样res = s[i]-dis[i]⑴。dis数组更新放在寻觅根结点递归的后面，由于要先更新父亲的再更新自己的。

#include <stdio.h>
const int N = 30005;
char str[5];
int p,pa[N],s[N],dis[N];

int get_parent(int x) {
    if (x != pa[x]) {
        int f = pa[x];
        pa[x] = get_parent(pa[x]);
        dis[x] += dis[f];
    }
    return pa[x];
}

int main() {
    int t;
    for (int i = 0; i <= N; i++) {
        pa[i] = i;
        s[i] = 1;
        dis[i] = 0;
    }
    scanf("%d",&t);
    while (t--) {
        scanf("%s",str);
        if (str[0] == 'M') {
            int a,b;
            scanf("%d%d",&a,&b);
            int px = get_parent(a);
            int py = get_parent(b);
            pa[py] = px;
            dis[py] = s[px];
            s[px] += s[py];
        }
        else {
            int a;
            scanf("%d",&a);
            int px = get_parent(a);
            printf("%d
",s[px] - dis[a] - 1);
        }
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!