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;
}