Richard21477 @ 2020-11-06 20:04:53
#include<bits/stdc++.h>
using namespace std;
// start from zero
int f[100010];
int father(int x){
return (x==f[x])?x:f[x]=father(f[x]);
}
int p[100010],ed[400050],ne[400050];
int cnt=1;
void insert(int u,int v){
ed[cnt]=v;
ne[cnt]=p[u];
p[u]=cnt++;
return;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int x,y;
for (int i=0;i<m;i++){
scanf("%d%d",&x,&y);
insert(x,y);
insert(y,x);
}
int k;
scanf("%d",&k);
bool ext[n];
int cut[k];
for (int i=0;i<n;i++)
ext[i]=true;
for (int i=0;i<n;i++)
f[i]=i;
for (int i=0;i<k;i++){
scanf ("%d",&cut[i]);
ext[cut[i]]=false;
}
int ans[k+1];
int cnt=n;
int u,v,fv,fu;
for (u=0;u<n;u++){
if (!ext[u]){
cnt--;
continue;
}
for (int i=p[u];i!=0;i=ne[i]){
v=ed[i];
if (!ext[v])
continue;
fu=father(u);
fv=father(v);
if (fu!=fv){
cnt--;
f[fu]=fv;
}
}
}
ans[k]=cnt;
for (int t=k-1;t>=0;t--){
//cut[i]
u=cut[t];
ext[u]=true;
cnt++;
for (int i=p[u];i!=0;i=ne[i]){
v=ed[i];
if (!ext[v])
continue;
fu=father(u);
fv=father(v);
if (fu!=fv){
cnt--;
f[fu]=fv;
}
}
ans[t]=cnt;
}
for (int i=0;i<=k;i++)
printf("%d\n",ans[i]);
//printf("\n");
return 0;
}
3RE1WA
by Richard21477 @ 2020-11-06 20:28:36
啊这
这道题第9个点WA/TLE的同学注意