题目描述

由于并查集不支持删除操作，这里可以逆向思维一波，使用反向并查集，
如果按照正序，求打击一次，二次连通块的数目，会超时，此时可以求将k次全部打击完的连通块数目，
接着将k-1次打击的点补上求连通块数目，一直补到第0次打击的数目，然后逆序输出就可。

样例

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7
输出
1
1
1
2
3
3

#include<iostream>
using namespace std;
const int N =400010;
int head[N],ans[N],p[N],d[N],idx=0;//头节点，答案，父亲，打击点
bool e[N];//是否被打击
//邻接表
struct edge{int u,v,next;}ed[400010];
//并查集
int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
//邻接表插入
void insert(int u,int v)
{
    ed[idx].u=u;
    ed[idx].v=v;
    ed[idx].next = head[u];
    head[u]=idx++;
}
int main()
{
    int n,m,k,tol,x,y,u;
    cin>>n>>m;
    //初始化
    for(int i=0;i<n;++i)
    {
        head[i]=-1;
        p[i]=i;
    }
    //m个点连接
    for(int i=0;i<m;++i)
    {
        cin>>x>>y;
        insert(x,y);
        insert(y,x);
    }
    cin>>k;
    tol = n-k;//打击k次后的点
    //记录打击
    for(int i =1;i<=k;++i)
    {
        cin>>x;
        d[i] =x;
        e[x]=true;
    }
    //先连通没有被打击的点
    for(int i =0;i<2*m;++i)
    {
        if(!e[ed[i].u]&&!e[ed[i].v])
        {
            int s = find(ed[i].u),t=find(ed[i].v);
            if(s!=t)
            {
                tol--;
                p[find(ed[i].u)]=find(ed[i].v);
            }
        }
    }
    //再一个个连接打击点
    ans[k+1]=tol;//打击k次的连通块

    //从打击k次算打击k-1次一直算到打击0次
    for(int j=k;j>=1;j--)
    {
        //修复点
        u=d[j];
        e[u]=false;
        tol++;
        //修复连接所有它所连接的点
        for(int i=head[u];i!=-1;i=ed[i].next)
        {
            if(!e[ed[i].v]&&find(ed[i].v)!=find(u))
            {
                tol--;
                p[find(ed[i].v)]=find(u);
            }
        }
        ans[j]=tol;
    }
    for(int i=1;i<=k+1;++i) cout<<ans[i]<<endl;
    return 0;
}