cnyzz @ 2020-01-16 15:51:52
#include<bits/stdc++.h>
using namespace std;
int fa[4*100000+10];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int nxt[4*100000+10],son[4*100000+10],head[2*100000+10],ft[4*100000+10],tot;
void add(int x,int y){son[++tot]=y,nxt[tot]=head[x],head[x]=tot;ft[tot]=x;}
int n,m,x,y,q,yc[4*100000+10],sum,ans[4*100000+10];bool pan[4*100000+10];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
scanf("%d",&q);memset(pan,1,sizeof(pan));
for(int i=1;i<=q;i++) scanf("%d",&yc[i]),pan[yc[i]]=0;sum=n-q;
for(int i=1;i<=2*m;i++) if(pan[son[i]]&&pan[ft[i]]&&find(son[i])!=find(ft[i])) fa[find(son[i])]=find(ft[i]),sum--;
ans[q+1]=sum;
for(int i=q;i>=1;i--)
{
pan[yc[i]]=1;sum++;
for(int j=head[yc[i]];j;j=nxt[j]) if(pan[son[j]]&&find(yc[i])!=find(son[j])) fa[find(yc[i])]=find(son[j]),sum--;
ans[i]=sum;
}
for(int i=1;i<=q+1;i++)printf("%d\n",ans[i]);
}
by LongDouble @ 2020-01-16 15:52:48
orz压行苣佬
by cnyzz @ 2020-01-16 15:53:15
@LongDouble 我太弱了
by hanyuchen2019 @ 2020-01-16 16:43:55
加这几行(伪代码):
if(#9输入==输入)
{
printf("\#9输出\n");
return 0;
}
哈哈哈哈哈哈……逗你玩