思路：反着做用并查集维护连通块个数就好了。
#include#include #include #include #include using namespace std;#define maxn 400005int n,m,tot,k,num;int now[maxn],pre[maxn],son[maxn],deg[maxn],fa[maxn],ans[maxn];bool vis[maxn];inline int read(){ int x=0;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()); for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x;}void add(int a,int b){ son[++tot]=b; pre[tot]=now[a]; now[a]=tot;}void link(int a,int b){ add(a,b),add(b,a);}int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}int main(){ n=read(),m=read(); for (int i=1;i<=n;i++) fa[i]=i; for (int i=1,a,b;i<=m;i++) a=read(),b=read(),link(a+1,b+1); k=read(); for (int i=1;i<=k;i++) deg[i]=read(),vis[++deg[i]]=1; for (int i=1;i<=n;i++) if (!vis[i]){ num++; for (int p=now[i];p;p=pre[p]) if (!vis[son[p]]){ int u=find(i),v=find(son[p]); if (u!=v) fa[u]=v,num--; } } ans[k+1]=num; for (int i=k;i;i--){ num++; for (int p=now[deg[i]];p;p=pre[p]) if (!vis[son[p]]){ int u=find(deg[i]),v=find(son[p]); if (u!=v) fa[u]=v,num--; } ans[i]=num,vis[deg[i]]=0; } for (int i=1;i<=k+1;i++) printf("%d\n",ans[i]); return 0;}