HDU 2818 – Building Block [带权并查集]

HDU题目链接

题意:有N堆积木,初始每堆积木有一个N号积木。给定两种操作:1.将含有a号积木的一堆移到含有b号积木的一堆之上  2.输出a号积木下面的积木数量。

分析:将每堆积木的最下边的作为根,每个根的儿子数作为权。每次移动积木的时候,路径压缩同步更新记录每个积木下面的数量。这种带权的并查集应该可以当做模板吧。

CPP代码如下:

 

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

const int maxn = 30005;

struct UFSet{
    int pa[maxn], cnt[maxn], under[maxn];
    void init() {
        memset(pa, -1, sizeof(pa));
        fill(cnt, cnt + maxn, 1);
        memset(under, 0, sizeof(under));
    }
    int root(int x) {
        int & px = pa[x];
        if(px == -1) return x;
        int rx = root(pa[x]);
        under[x] += under[px];
        return px = rx;
    }
    bool join(int u, int v) {
        int ru = root(u), rv = root(v);
        if(ru == rv) return false;
        pa[ru] = rv;
        under[ru] = cnt[rv];
        cnt[rv] += cnt[ru];
        cnt[ru] = 0;
        return true;
    }
}s;

int main() {
    s.init();
    int n; cin >> n;
    while (n--) {
        char op; int x, y; cin >> op;
        if(op == 'M') {
            cin >> x >> y;
            s.join(x, y);
        }
        else {
            cin >> x;
            s.root(x);
            cout << s.under[x] << endl;
        }
    }
    return 0;
}

欢迎留言