题目

分析

分析题意

一开始没读懂题
题目的意思是：
一开始一张完整的图，然后点直接存在一些边
接着摧毁一些点（摧毁一个点指摧毁这个点和点的边）

关键思想

逆向法
从最后留下的点开始（这里有个易错点）
然后从后往前加点回来，维护一个数表示当前的连通集个数
每合并一次就连通集个数减1

《合并》 《连通集》 想到并查集

易错点

起初从没被删去的点开始

一开始这些点并不一定是单独的，记得判断

下列的备注那里我一开始没写

我想着新加的点都是独立的点
但是记得新加的点是可能有多次连边，一开始独立，后面可就不独立了

for(int i=k;i>=1;i--){
    cur++;
    int t=dot[i];
    erase[t]=false;
    for(int j=h[t];j!=-1;j=ne[j]){
        int a=e[j];
        if(erase[a]==true) continue;
        int fa=find(a);
        int ft=find(t);//这里得写！！！！ 
        if(fa!=ft){
            f[ft]=fa;
            cur--;
        }
    }
    sta.push(cur);
}

一开始我的判断写的不是if(fa!=ft)

因为为了防止连的是同一个连通集的，专门设置了bool数组，用于把哪些代表祖先所在的集合已经被合并过，那么再次合并，是不会使连通集数量减少的
但是这样会tle！！！（因为每次要把bool数组恢复为false）
正确的方法是：
直接判断对t也查找父结点，如果ft和fa一样，说明本来就在一个集合，那么连边不会使并查集个数少1，这个思想很重要！！！！

#include <bits/stdc++.h>
using namespace std;

const int N=4e5+7;
const int M=2e5+7;

int n,m;
int h[N],e[M*2],ne[M*2],idx;

int dot[N],k;
bool erase[N];
bool st[N];
int f[N];

void insert(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}


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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i=0;i<n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        insert(x,y);insert(y,x);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d",&dot[i]);
        erase[dot[i]]=true;
    }
    int cur=0;
    for(int i=0;i<n;i++){
        if(erase[i]==false) cur++;
    }
    for(int i=0;i<n;i++){
        if(erase[i]==false){
            for(int j=h[i];j!=-1;j=ne[j]){
                int dq=e[j];
                if(erase[dq]==true) continue;
                int fdq=find(dq);
                int fi=find(i);
                if(fdq!=fi){
                    f[fdq]=fi;
                    cur--;
                }
            }
        }
    }
    stack<int> sta;
    sta.push(cur);
    for(int i=k;i>=1;i--){
        cur++;
        int t=dot[i];
        erase[t]=false;
        for(int j=h[t];j!=-1;j=ne[j]){
            int a=e[j];
            if(erase[a]==true) continue;
            int fa=find(a);
            int ft=find(t);//这里得写！！！！ 
            if(fa!=ft){
                f[ft]=fa;
                cur--;
            }
        }
        sta.push(cur);
    }
    while(sta.empty()==false){
        int x=sta.top();
        sta.pop();
        printf("%d\n",x);
    }
    return 0;
}