POJ 1988 Cube Stacking （带权并查集）

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

题目链接：Cube Stacking

num数组表示集合个数，under表示比他小的个数即可

代码：

#include <stdio.h>
#include <string.h>const int N = 30005;
int p, a, b, parent[N], under[N], num[N];
char q[2];void init() {for (int i = 1; i < N; i++) {parent[i] = i;under[i] = 0;num[i] = 1;}
}int find(int x) {if (parent[x] == x)return x;int px = find(parent[x]);under[x] += under[parent[x]];return parent[x] = px;
}int main() {while (~scanf("%d", &p)) {init();while (p--) {scanf("%s", q);if (q[0] == 'M') {scanf("%d%d", &a, &b);int pa = find(a), pb = find(b);if (pa != pb) {parent[pa] = pb;under[pa] += num[pb];num[pa] += num[pb];num[pb] = num[pa];}}else {scanf("%d", &a);find(a);printf("%d\n", under[a]);}}}return 0;
}

这篇关于POJ 1988 Cube Stacking （带权并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---