yyyh_h @ 2022-12-24 11:30:11
#include<bits/stdc++.h>
#define maxm 200000
#define maxn 2*maxm
using namespace std;
struct edge
{
int x,y;
}e[maxm+10];
int fa[maxn+10];
int del[maxn+10];
int ans[maxn+10];
bool f[maxn+10];
int n,m,k,p=0;
inline int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void unite(int x,int y)
{
fa[find(x)]=find(y);
}
inline void init()
{
for(int i=0;i<n;i++)
if(!f[i])
{
fa[i]=i;
}
}
vector<int>g[maxn+10];
inline int get_ans()
{
bool flag=0,flag2=0;
int st[maxn+10];
int ans_=1,s=1;
st[1]=find(p);
for(int i=0;i<n;i++)
if(!f[i] and i!=p)
{
flag=0;
flag2=0;
int l=find(i);
for(int j=1;j<=s;j++)
{
if(st[j]!=l and !flag2)
{
flag=1;
}
else if(st[j]==l)
{
flag=0;
flag2=1;
break;
}
}
if(flag) st[++s]=l,ans_++;
}
return ans_;
}
int main()
{
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
e[i]=(edge){a,b};
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&del[i]);
f[del[i]]=1;
}
init();
for(int i=1;i<=m;i++)
{
int a=e[i].x,b=e[i].y;
if(f[a]) g[a].push_back(b);
if(f[b]) g[b].push_back(a);
if(!f[a] and !f[b]) unite(a,b),p=a;
}
ans[k]=get_ans();
for(int i=k;i>=1;i--)
{
int a=del[i];
fa[a]=a;
f[a]=0;
for(int j=0;j<g[a].size();j++)
if(!f[g[a][j]])
{
int b=g[a][j];
unite(a,b);
}
ans[i-1]=get_ans();
}
for(int i=0;i<=k;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}
code