uva 1329 - Corporative Network(加权并查集)

题目链接：uva 1329 - Corporative Network

题目大意：有n个节点，初始时每个节点的父节点都不存在，每次执行一个I操作和E操作：

• I操作：吧节点u的父节点设为v，距离为|u-v| % 1000，输入保证u没有父节点
• E操作：询问u到根节点的距离。

解题思路：裸的加权并查集。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;
const int maxn = 20005;
const int MOD = 1000;

int N, f[maxn], d[maxn];

int getfar (int x) {
    if (x == f[x])
        return x;

    int root = getfar(f[x]);
    d[x] += d[f[x]];
    return f[x] = root;
}

int main () {
    int cas;
    scanf("%d", &cas);

    while (cas--) {
        scanf("%d", &N);
        for (int i = 0; i <= N; i++) {
            f[i] = i;
            d[i] = 0;
        }

        int u, v;
        char str[10];
        while (scanf("%s", str), str[0] != 'O') {
            if (str[0] == 'E') {
                scanf("%d", &u);
                getfar(u);
                printf("%d\n",  d[u]);
            } else if (str[0] == 'I') {
                scanf("%d%d", &u, &v);
                f[u] = v;
                d[u] = abs(u - v) % MOD;
            }
        }
    }
    return 0;
}