题解

#include<iostream>
#include<vector>
using namespace std;
struct DSU{
    vector<int> fa , siz;

    void init(int n){
        fa.resize(n + 1);
        siz.resize(n + 1);
        for(int i = 1 ; i <= n ; i++){
            fa[i] = i;//初始化，默认上级是自己
            siz[i] = 1;//当前集合只有自己，大小默认为1
        }
    }
    //构造函数，直接初始化
    DSU(int n){
        init(n);
    }
    int find(int x){
        if(fa[x] == x){
            //当前集合的牢大是他自己
            return x;
        }
        else{
            //向上级接着去找
            //发动技能，忘本
            //路径压缩，把当前节点直接认牢大为上级
            fa[x] = find(fa[x]);
            return fa[x];
        }
    }
    //启发式合并 
    //从小合并到大
    //启发式合并之后，集合的深度最大为 logn
    bool merge(int x , int y){
        //第一步：先找到集合的牢大
        int fx = find(x);
        int fy = find(y);
        if(fx == fy){//不需要合并
            return false;
        }
        //如果不一样，发动技能，合并，认别人为牢大
        //默认集合大小较大的为牢大
        if(siz[fx] < siz[fy]){
            swap(fx , fy);
        }
        //默认fx是比较大的
        fa[fy] = fx;//认fx为上级
        siz[fx] += siz[fy];//合并集合大小
        siz[fy] = 0;//fy集合被合并了，大小置为0
        return true;
    }
    bool same(int x , int y){
        return find(x) == find(y);
    }
    int size(int x){
        return siz[find(x)];
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n , m;
    cin >> n >> m;
    vector<vector<int>> edge(n + 1);
    for(int i = 1 ; i <= m ; i ++){
        int x , y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    int k;
    cin >> k;
    vector<int>att(k + 1 , 0);
    vector<int>exist(n + 1 , 1);
    //炸
    for(int i = 1 ; i <= k ; i ++){
        cin >> att[i];
        exist[att[i]] = 0; // 删除
    }
    //所有攻击完的情况
    DSU dsu(n + 1);
    int cnt = n - k;
    for(int i = 1 ; i <= n ; i ++){
        if(exist[i]){
            for(auto j : edge[i]){
                if(exist[j]){
                    cnt -= dsu.merge(i , j);
                }
            }
        }
    }
    //此时代表了第 k 次攻击完的情况
    vector<int> ans(k + 1 , 0);
    ans[k] = cnt;//记录答案
    for(int i = k ; i >= 1 ; i --){
        //复活第 att[i] 颗星球
        exist[att[i]] = 1;
        //复活成功，联通快个数 + 1
        cnt ++;
        for(auto v : edge[att[i]]){
            if(exist[v]){
                cnt -= dsu.merge(att[i] , v);
            }
        }
        //复活了第 i 个被攻击的星球
        //此时代表了第 i - 1 次攻击以后
        ans[i - 1] = cnt;
    }
    for(int i = 0 ; i <= k ; i ++)
        cout << ans[i] << "\n";
    return 0;
}