http://acm.hdu.edu.cn/showproblem.php?pid=2473
给定两种操作
第一种是合并X Y
第二种是把X分离出来，就是从原来的集合中分离出来，其它的关系不变。
关键是怎么分离，可以考虑把它变成一个其它值。HASH[i] = other_val
然后用新值去做并查集即可、
需要注意的一点就是
假如现在根是1，fa[1] = 1, fa[2] = 1, fa[3] = 1
那么如果你删除了1，这应该输出2.但是现在是fa[2] = 1，是一个不存在的根了，这个时候ans应该+1，但是按照并查集的思路
if (find(HASH[i]) == HASH[i]) ans++ 是不行的，因为这个根已经不存在了。
解决方法就是标记是否为虚根，del[i] = true表示删除了，但是枚举fa[3]的时候就要避免重新加，需要取消标记。
如果这时再有M 4 2，那么就把fa[4] = 1，用虚根表示即可。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 2e6 + ;
int fa[maxn];
int HASH[maxn];
bool del[maxn];
void init() {
memset(del, , sizeof del);
for (int i = ; i < maxn; ++i) fa[i] = i;
for (int i = ; i < maxn; ++i) HASH[i] = i;
}
int find(int u) {
if (fa[u] == u) return u;
else return fa[u] = find(fa[u]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[y] = x;
}
}
int n, m;
int ff;
void work() {
init();
int t = n;
for (int i = ; i <= m; ++i) {
char str[];
int a, b;
scanf("%s", str);
if (str[] == 'M') {
scanf("%d%d", &a, &b);
merge(HASH[a], HASH[b]);
} else {
scanf("%d", &a);
del[HASH[a]] = ;
HASH[a] = n++;
}
}
int ans = ;
for (int i = ; i < t; ++i) {
if (find(HASH[i]) == HASH[i]) ans++;
if (del[find(HASH[i])]) {
del[find(HASH[i])] = ;
ans++;
}
}
// cout << find(2) << endl;
printf("Case #%d: %d\n", ++ff, ans);
return;
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d%d", &n, &m) != EOF && (n + m)) {
work();
}
return ;
}
4 7
M 0 1
M 2 3
M 1 3
S 1
S 2
S 3
S 0
3 3
M 0 1
M 0 2
S 0
给些数据