UVA - 1329 Corporative Network

浏览数：23 / 时间：2015年06月09日

题意：有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