UVALive - 3027Corporative Network（带权并查集）

本文主要是介绍UVALive - 3027Corporative Network（带权并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目： 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;
}

 

这篇关于UVALive - 3027Corporative Network（带权并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---