提高+/省选-
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=500005;
struct edge
{
int u,v,next;
}e[N];
int head[N],cnt;
void add(int u,int v)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int a[N],fa[N],ans[N],sum;
bool b[N];
int find(int x)
{
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
int main(int argc, char const *argv[])
{
int n,m,k;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&a[i]);
b[a[i]]=1;
}
sum=n-k;
for(int i=0;i<n;i++) //未被破坏的点中有可以连通的
{
if(!b[i]) //错误点：枚举的是每个点是否被破坏，不是b[a[i]]，a[i]存的是被破坏的点
{
for(int j=head[i];j;j=e[j].next)
{
int v=e[j].v;
int x=find(i);
int y=find(v);
if(!b[v] && x!=y)
{
fa[x]=y;
sum--;
}
}
}
}
ans[k+1]=sum;
for(int i=k;i;i--) //逆序建立边
{
int u=a[i];
b[u]=0;
sum++;
for(int j=head[u];j;j=e[j].next)
{
int v=e[j].v;
int x=find(u);
int y=find(v);
if(!b[v] && x!=y)
{
fa[x]=y;
sum--;
}
}
ans[i]=sum;
}
for(int i=1;i<=k+1;i++)
printf("%d\n",ans[i]);
return 0;
}
星球大战
原文：https://www.cnblogs.com/kavinblog/p/12534814.html
