带删并查集

Link

前置知识

• 基础的并查集

题意简述

• 给定点的个数 $n$ ，操作的个数 $m$ ，维护一个支持删除操作的并查集。
• 对于每一组测试数据，输出剩余集合数。
• $n \leq 1e5$, $m \leq 1e6$

题目分析

对于合并两个集合的操作，显然可以想到并查集。

int find(int a) {
    if (f[a] == a) return a;
    return f[a] = find(f[a]);
}

inline void merge(int a, int b) {
    f[find(a)] = find(b); // 路径压缩
}

然而，这道题的关键点是实现删除操作。

首先考虑直接删，但是显然有可能改变原来并查集的结构。

有什么办法可以避免这个问题呢？这个时候我们可以使用造假点的办法。

在构造时使用假点，删点时将原点指向另一假点。

对于查询部分，只要扫一遍真点，桶排思想找根即可。

以下代码，个人码风不喜勿喷

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int f[10000005];
int b[10000005]; // 用于查询
int cnt, ans;

int find(int a) {
    if (f[a] == a) return a;
    return f[a] = find(f[a]);
}

inline void merge(int a, int b) {
    f[find(a)] = find(b); // 路径压缩
}

inline void init(int n, int m) {
    cnt = 2 * n;
    ans = 0;
    for (register int i=0; i<n; ++i) f[i] = n+i;
    for (register int i=n; i<=cnt+m; ++i) f[i] = i;
    memset(b, 0, sizeof(b));
}

inline void del(int x) { // 删点
    f[x] = cnt++;
}

inline int read() {
    register int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}

int main() {
    int n, m;
    char cmd[6];
    int x, y;

    int i = 0;
    while (true) {
        n=read(), m=read();

        if (!n && !m) break;
        init(n, m);
        ++i;

        while (m--) {
            scanf("%s", cmd+1);

            if (cmd[1] == 'M') {
                x = read(), y = read();
                merge(x, y);
            }
            else { // 'S'
                del(read());
            }
        }

        for (int k=0; k<n; ++k) { // 查询
            int tmp = find(f[k]);
            if (!b[tmp]) ++ans, b[tmp] = 1;
        }

        printf("Case #%d: %d\n", i, ans);
    }

    return 0;
}

Tips: 如果你的代码莫名其妙WA，请注意读入操作和循环上下界。笔者为调试这两个问题花了几天，可能是我太蒻了吧。