POJ1988 Cube Stacking

nums数组维护每个堆的元素个数，当不同的两个堆合并时，要加上nums，相同堆合并时则不需要

#include <iostream>
using namespace std;
const int maxn = 30010;
struct node {
    int pre;
    int num;
}arr[maxn];
int nums[maxn];
void init() {
    for (int i = 0; i < maxn; i++) {
        arr[i].pre = i;
        arr[i].num = 0;
        nums[i] = 1;
    }
}
int find(int x) {
    if (x == arr[x].pre)return x;
    int temp = arr[x].pre;
    arr[x].pre = find(temp);
    arr[x].num += arr[temp].num;
    return arr[x].pre;
}

int main()
{
    int n;
    cin >> n;
    init();
    while (n--) {
        char c;
        cin >> c;
        if (c == 'M') {
            int num1, num2;
            cin >> num1 >> num2;
            int fa = find(num1);
            int fb = find(num2);
            if (fa == fb) {
                arr[num1].num += arr[num2].num;
            }
            else {
                arr[fa].pre = fb;
                arr[fa].num += nums[fb];
                nums[fb] += nums[fa];
            }
        }
        else {
            int num3;
            cin >> num3;
            find(num3);
            cout << arr[num3].num << endl;
        }
    }
}