[BZOJ1015] [JSOI2008]星球大战starwar
我又双叒叕被自己坑了...
BZOJ数据有点毒瘤,建议自己卡卡常，不过Luogu上很轻松的跑过了
还是比较简单的一题...
正向删点很难，所以我们考虑反着来，咱往里面加点
要注意的是，那些还没加进去的点是不算连通块个数的...不过估计就我这种rui zhi注意就够了
1 #include<cstdio> 2 #include<queue> 3 #include<iostream> 4 #include<cstring> 5 #include<vector> 6 #include<algorithm> 7 using namespace std; 8 inline int read(){ 9 int ans=0,f=1;char chr=getchar(); 10 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 11 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 12 return ans*f; 13 }int n,m,fa[2000005],k,vis[2000005],p[2000005],ANS[2000005]; 14 vector<int> v[2000005]; 15 int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);} 16 int main(){ 17 n=read();m=read(); 18 for(int i=1;i<=n+1;i++) fa[i]=i; 19 for(int i=1;i<=m;i++){ 20 int x=read(),y=read();++x,++y; 21 v[x].push_back(y);v[y].push_back(x); 22 }k=read(); 23 for(int i=1;i<=k;i++) p[k-i+1]=read(),++p[k-i+1],vis[p[k-i+1]]=1; 24 for(int i=1;i<=n;i++)if(!vis[i]) 25 for(int j=0;j<v[i].size();j++){ 26 if(vis[v[i][j]]) continue; 27 int fx=find(i),fy=find(v[i][j]); 28 if(fx!=fy) fa[fx]=fy; 29 } 30 for(int i=1;i<=n;i++) if(!vis[i]&&fa[i]==i) ANS[1]++; 31 for(int i=1,t;i<=k;i++){t=ANS[i]; 32 vis[p[i]]=0; 33 for(int j=0;j<v[p[i]].size();j++){ 34 if(vis[v[p[i]][j]]) continue; 35 int fx=find(p[i]),fy=find(v[p[i]][j]); 36 if(fx!=fy) fa[fx]=fy,--t; 37 }ANS[i+1]=t+1; 38 }reverse(ANS+1,ANS+k+2); 39 for(int i=1;i<=k+1;i++) cout<<ANS[i]<<endl; 40 return 0; 41 }
