luogu_1197 [JSOI2008]星球大战

#include <cstdio>#include <iostream>#include <vector>using namespace std;const int N=400020;const int M=200010;int p[N],n,m,k,a[M],sum,ans[M];vector<int> G[N];bool b[N];int find(int x){return x==p[x]?x:p[x]=find(p[x]);}int main(){ ???scanf("%d%d",&n,&m); ???for(int i=1;i<=n;i++)p[i]=i; ???for(int i=1;i<=m;i++){ ???????int x,y; ???????scanf("%d%d",&x,&y); ???????G[x].push_back(y); G[y].push_back(x); ???} ???scanf("%d",&k); sum=n-k; ???for(int i=1;i<=k;i++){scanf("%d",&a[i]); b[a[i]]=1;} ???for(int i=1;i<=n;i++){ ???????if(b[i])continue; ???????for(int j=0;j<G[i].size();j++){ ???????????int v=G[i][j]; ???????????if(find(v)!=find(i) && b[v]==0){ ???????????????sum--; ???????????????p[find(v)]=find(i); ???????????} ???????} ???} ???for(int i=k;i>=0;i--){ ???????ans[i]=sum; sum++; b[a[i]]=0; ???????for(int j=0;j<G[a[i]].size();j++){ ???????????int v=G[a[i]][j]; ???????????if(find(v)!=find(a[i]) && b[v]==0){ ???????????????sum--; ???????????????p[find(v)]=find(a[i]); ???????????} ???????} ???} ???for(int i=0;i<=k;i++)printf("%d\n",ans[i]); ???return 0;}