UVALive - 3027Corporative Network（带权并查集）
浏览数：50 /
时间：2015年06月09日
题目： UVALive - 3027Corporative Network（带权并查集）
题目大意：有n和节点，初始时每个节点的父节点都不存在，然后有下面两种操作：I 操作 I a，b 将a的父节点变成b。E操作 E a，查询a到它的父节点的距离。
解题思路：带权并查集。注意这里距离的变化是a -> b，那么a到根节点的距离就是a到b的距离的绝对值 % 1000 + b到它的根节点的距离。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int p[maxn], c[maxn];
int n;
void init () {
for (int i = 1; i <= n; i++) {
p[i] = i;
c[i] = 0;
}
}
int getParent (int a) {
if (a == p[a])
return a;
int t = p[a];
p[a] = getParent (p[a]);
c[a] += c[t];
return p[a];
}
int main () {
int T;
int a, b;
char str[10];
scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
init();
while (scanf ("%s", str) != EOF) {
if (str[0] == 'O')
break;
if (str[0] == 'E') {
scanf ("%d", &a);
int q1 = getParent (a);
printf ("%d\n", c[a]);
} else {
scanf ("%d%d", &a, &b);
p[a] = b;
c[a] = abs (a - b) % 1000;
}
}
}
return 0;
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
