Cwling @ 2020-08-16 18:42:03
样例未过
#include <bits/stdc++.h>
#define MAXN 1000001
using namespace std;
inline int read()
{
int r=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*f;
}
struct p{
int next,to,from;
}edge[MAXN];
int num_edge;
int head[MAXN];
int b[MAXN];
int f[MAXN];
int anss[MAXN];
void add(int from,int to)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
edge[num_edge].from=from;
head[from]=num_edge;
}
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
void unionn(int x,int y)
{
f[x]=y;
return;
}
int ans;
int main() {
int n=read(),m=read();
for(int i=1;i<=n;++i)
f[i]=i;
for(int i=1;i<=m;++i)
{
int x=read(),y=read();
add(x,y),add(y,x);
}
int k=read();
ans=n-k;
for(int i=1;i<=k;++i)
{
f[i]=read();
b[f[i]]=true;
}
for(int i=1;i<=n;++i)
{
for(int j=head[i];j;j=edge[j].next)
{
int v=edge[j].to;
if(!b[i]&&!b[v])
{
int k1=find(i),k2=find(v);
if(k1!=k2)
{
unionn(k1,k2);
ans--;
}
}
}
}
anss[k+1]=ans;
for(int i=k;i>=1;--i)
{
b[f[i]]=false;
ans++;
int k1=find(f[i]);
for(int j=head[f[i]];j;j=edge[j].next)
{
int v=edge[j].to;
if(!b[v])
{
int k2=find(v);
if(k1!=k2)
{
unionn(k1,k2);
ans--;
}
}
}
anss[i]=ans;
}
for(int i=1;i<=k+1;++i)
cout<<anss[i]<<endl;
return 0;
}
by Cwling @ 2020-08-16 20:14:19
救救孩子