题目大意

有一个图，依次删去一些点后有多少个连通块。

思路

一道并查集 + 离线 的题目。

这道题第一眼肯定是想如何维护可以删除节点的并查集，但是这样不太可做。（或许是我太菜了。）但是我们发现他只有一个删除的操作，没有增加的操作，那么就可以想到离线计算。

离线计算，也就是把原本是读入后立马运算的操作都存起来，再算。

这样的好处就是我们可以按操作倒着来，最后再正着输出。

到着来后这道题就是一个类似模板的并查集。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n, m;
int f[1000005], kil[1000005], nalive[1000005];
int find(int x) {
    return (f[x] == x ? (x) : f[x] = find(f[x]));
}
vector <int> e[400005];
struct node {
    int x, y;
} e2[1000005];
int sum = 0;
int ans[1000005], k;
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int x, y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
        e2[i] = (node){x, y};
    }
    for (int i = 1; i <= n; i ++) {
        f[i] = i;
    }
    cin >> k;
    for (int i = 1; i <= k; i ++) {
        cin >> kil[i];
        nalive[kil[i]] = 1;
    }
    sum = n - k;
    for (int i = 1; i <= m; i ++) {

        if (nalive[e2[i].x] == 0 && nalive[e2[i].y] == 0 && (find(f[e2[i].x]) != find(f[e2[i].y]))) {
            sum --;
            f[find(f[e2[i].x])] = find(f[e2[i].y]);
        }
    }
    // cout << sum << "\n";
    // for (int i = 1; i <= n; i ++) cout << f[i] << " ";
    // cout << "\n";
    ans[k + 1] = sum;
    for (int i = k; i >= 1; i --) {
        // cout << sum << " ";
        int fr = kil[i];
        sum ++;
        nalive[fr] = 0;
        for (int j = 0; j < e[fr].size(); j ++) {
            int to = e[fr][j];
            // cout << fr << " " << to << " " << nalive[fr] << " " << nalive[to] << "\n";

            if (nalive[to] == 0 && find(f[fr]) != find(f[to])) {
                sum --;
                f[find(f[fr])] = find(f[to]);
            }
        }
        ans[i] = sum;
    }

    for (int i = 1; i <= k + 1; i ++) cout << ans[i] << "\n";
    return 0;
}