Cure_Wing @ 2023-02-01 14:09:49
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using std::cin;using std::cout;
constexpr int M=200005;
int n,m,x[M],y[M],k,a[M<<1],fa[M<<1],ans[M<<1];
bool vis[M<<1];
std::vector<int>edge[M<<1];
inline int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
inline bool add(int u,int v){
int fu=find(u),fv=find(v);
if(fu==fv) return 0;
fa[fv]=fu;
return 1;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;++i){
cin>>x[i]>>y[i];
++x[i];++y[i];
edge[x[i]].push_back(y[i]);
edge[y[i]].push_back(x[i]);
}
cin>>k;
for(int i=1;i<=k;++i){
cin>>a[i];
++a[i];
vis[a[i]]=1;
}
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i)
if(!vis[x[i]]&&!vis[y[i]])
add(x[i],y[i]);
for(int i=1;i<=n;++i) ans[k]+=(fa[i]==i)&&(!vis[a[i]]);
for(int i=k;i>=1;--i){
ans[i-1]=ans[i]+1;
for(auto j:edge[a[i]])
if(!vis[j])
ans[i-1]-=add(j,a[i]);
vis[a[i]]=0;
}
for(int i=0;i<=k;++i) cout<<ans[i]<<'\n';
return 0;
}
by Cure_Wing @ 2023-02-01 16:19:18
for(int i=1;i<=n;++i) ans[k]+=(fa[i]==i)&&(!vis[i]);
此贴完结。