!!!A @ 2023-09-30 10:34:29
#include<bits/stdc++.h>
using namespace std;
int n,k,m,u,v,p,q,op;
int f[1000001];
int jl[1000001];
bool pd[1000001],kp;
int del[1000001];
int ans;
int anss[100001],ansk;
struct aaaa
{
int l;
int r;
}ma[1000001];
bool cmp(aaaa xx,aaaa yy)
{
if(xx.l==yy.l)
{
return xx.r<yy.r;
}
return xx.l<yy.l;
}
inline int gf(int xx)
{
if(f[xx]==xx)
{
return xx;
}
return f[xx]=gf(f[xx]);
}
int main()
{
cin>>n>>m;
for(int i=0; i<n; i++)
{
f[i]=i;
}
for(int i=1; i<=m; i++)
{
cin>>u>>v;
ma[i*2-1].l=u;
ma[i*2-1].r=v;
ma[i*2].l=v;
ma[i*2].r=u;
}
sort(ma+1,ma+2*m+1,cmp);
for(int i=1; i<=2*m; i++)
{
jl[ma[i].l]++;
}
for(int i=1; i<n; i++)
{
jl[i]+=jl[i-1];
}
scanf("%d",&k);
for(int i=1; i<=k; i++)
{
scanf("%d",&del[i]);
pd[del[i]]=true;
}
for(int i=0; i<n; i++)
{
if(pd[i])
{
continue;
}
if(i==0)
{
for(int j=1; j<=jl[0]; j++)
{
if(pd[ma[j].r]==true)
{
continue;
}
p=gf(ma[j].l);
q=gf(ma[j].r);
f[p]=q;
}
continue;
}
for(int j=jl[i-1]+1; j<=jl[i]; j++)
{
if(pd[ma[j].r]==true)
{
continue;
}
p=gf(ma[j].l);
q=gf(ma[j].r);
f[p]=q;
}
}
for(int i=0; i<n; i++)
{
if(pd[i]==true)
{
continue;
}
gf(i);
if(i==f[i])
{
ans++;
}
}
ansk++;
anss[ansk]=ans;
for(int i=k; i>=1; i--)
{
kp=false;
pd[del[i]]=false;
op=del[i];
if(op==0)
{
for(int j=1; j<=jl[0]; j++)
{
if(pd[ma[j].r]==true)
{
continue;
}
p=gf(ma[j].l);
q=gf(ma[j].r);
if(kp && p!=q)
{
ans--;
}
f[p]=q;
kp=true;
}
continue;
}
for(int j=jl[op-1]+1; j<=jl[op]; j++)
{
if(pd[ma[j].r]==true)
{
continue;
}
p=gf(ma[j].l);
q=gf(ma[j].r);
if(kp && p!=q)
{
ans--;
}
f[p]=q;
kp=true;
}
ansk++;
anss[ansk]=ans;
}
for(int i=ansk; i>=1; i--)
{
cout<<anss[i]<<endl;
}
return 0;
}
by andy_2005 @ 2023-12-04 22:22:57
153行超短代码