[lnsyoj1015/luoguP1197/JSOI2008]星球大战starwar

题意

给出一个 \(n\) 个点，\(m\) 条边的无向图，对其进行 \(k\) 次操作，每次操作会删除一个当前无向图中存在的点及其相邻的边，求原图 和每次操作之后的图的连通块个数

sol

由于需要计算连通块个数，可以自然的想到使用并查集解决。然而，删除某个点后，我们无法通过并查集快速地得知其与其他点是否直接联通，也就无法快速地计算。
考虑按照操作的逆序来计算，那么就相当于在一个 \(n-k\) 个点的无向图中，每次操作添加一个点，并添加一些与其相邻的边，求原图和每次操作之后的图的连通块个数。这样，就可以通过并查集来解决这个问题了。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <vector>

#define x first 
#define y second 

using namespace std;
typedef pair<int, int> PII;

const int N = 400005;

int n, m, k;
int g[N];
PII edges[N];
unordered_map<int, int> depth;
vector<PII> edge[N];
int fa[N];
int ans[N];

int find(int x){
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++ ) {
        int x, y;
        scanf("%d%d", &x, &y);
        edges[i] = {x, y};
    }

    scanf("%d", &k);
    for (int i = 1; i <= k; i ++ ) {
        scanf("%d", &g[i]);
        depth[g[i]] = k - i + 1;
    }
    
    for (int i = 1; i <= m; i ++ ) {
        int dx = depth[edges[i].x], dy = depth[edges[i].y];
        edge[max(dx, dy)].push_back(edges[i]);
    }

    for (int i = 1; i <= n; i ++ ) fa[i] = i;
    int cnt = n - k;

    for (int d = 0; d <= k; d ++ , cnt ++ ){
        // printf("#depth: %d\n", d);
        for (auto e : edge[d]){
            // printf("%d %d\n", e.x, e.y);
            int fx = find(e.x), fy = find(e.y);
            if (fx == fy) continue;
            cnt -- ;
            fa[fx] = fy;
        }

        ans[d] = cnt;
    }

    for (int i = k; i >= 0; i -- ) printf("%d\n", ans[i]);

    return 0;
}