UVA - 1329 Corporative Network

题意：有n个节点，初始话每个节点的父节点都是不存在的，你的任务是执行I或者E操作

I：u,v将u的父节点设为v ，距离为|u-v|%1000； E：询问u到根节点的距离

输出每条E操作

思路：在并查集的基础上加上路径的压缩

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int mod = 1000;
const int MAXN = 20005;

int d[MAXN],f[MAXN],n;

int find(int x){
    if (f[x] != x){
        int root = find(f[x]);
        d[x] += d[f[x]]; 
        return f[x] = root;
    }
    else return x;
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        for (int i = 0; i <= n; i++)
            f[i] = i,d[i] = 0;
        int u,v;
        char op;
        while (cin >> op && op != ‘O‘){
            if (op == ‘I‘){
                scanf("%d%d",&u,&v);
                f[u] = v;
                d[u] = abs(u-v) % mod;
            }
            else {
                scanf("%d",&u);
                find(u);
                printf("%d\n",d[u]);
            }
        }
    }
    return 0;
}

UVA - 1329 Corporative Network

原文：http://blog.csdn.net/u011345136/article/details/19421549