UVA 11987 - Almost Union-Find(并查集)

UVA 11987 - Almost Union-Find

题目链接

题意:给定一些集合,操作1是合并集合,操作2是把集合中一个元素移动到还有一个集合,操作3输出集合的个数和总和

思路:并查集,关键在于操作2,对于并查集,要去除掉一个结点,假设该结点不是根那就好办了,那么就多开n个结点,每一个结点初始父亲都是它的i + n,这样在移动的时候,就不用操心他是根结点了剩下就是普通的带权并查集了

代码:

#include <cstdio>
#include <cstring> const int N = 200005; int n, m, parent[N], num[N], sum[N]; int find(int x) {
return x == parent[x] ? x : parent[x] = find(parent[x]);
} void init() {
for (int i = 0; i <= n; i++) {
parent[i] = parent[i + n] = i + n;
sum[i] = sum[i + n] = i;
num[i] = num[i + n] = 1;
}
} int main() {
while (~scanf("%d%d", &n, &m)) {
int q, a, b;
init();
while (m--) {
scanf("%d", &q);
if (q == 1) {
scanf("%d%d", &a, &b);
int pa = find(a);
int pb = find(b);
if (pa == pb) continue;
parent[pa] = pb;
num[pb] += num[pa];
sum[pb] += sum[pa];
}
else if (q == 2) {
scanf("%d%d", &a, &b);
int pa = find(a);
int pb = find(b);
if (pa == pb) continue;
parent[a] = pb;
num[pa]--;
num[pb]++;
sum[pa] -= a;
sum[pb] += a;
}
else {
scanf("%d", &a);
int pa = find(a);
printf("%d %d\n", num[pa], sum[pa]);
}
}
}
return 0;
}
上一篇:Qt多工程多目录的编译案例


下一篇:mysql-数据(记录)相关操作(增删改查)及权限管理