HDU 2473 Junk-Mail Filter 并查集，虚拟删除操作

#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 + 20;
int fa[maxn];
int HASH[maxn];
bool del[maxn];
void init() {
    memset(del, 0, sizeof del);
    for (int i = 0; i < maxn; ++i) fa[i] = i;
    for (int i = 0; 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 = 1; i <= m; ++i) {
        char str[11];
        int a, b;
        scanf("%s", str);
        if (str[0] == ‘M‘) {
            scanf("%d%d", &a, &b);
            merge(HASH[a], HASH[b]);
        } else {
            scanf("%d", &a);
            del[HASH[a]] = 1;
            HASH[a] = n++;
        }
    }
    int ans = 0;
    for (int i = 0; i < t; ++i) {
        if (find(HASH[i]) == HASH[i]) ans++;
        if (del[find(HASH[i])]) {
            del[find(HASH[i])] = 0;
            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 0;
}