题目
题解
判断两个星球的连通性以及计算连通块的个数，可以使用并查集。但是，并查集不容易实现删除操作，所以要从问题的反面考虑，即从最终的局面开始，逐个添加被消灭的星球。实时计算连通块的数量，若两个连通块合并，则数量减一。
一些与题目本身无关的提醒：定义vector<int> v后，如果容器是空的，不能用v[]=直接赋值，如果容器内有超过i个元素（即v[i]存在），才可以直接访问v[i]。 变量名不要用kill（与库函数重名？）。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <bits/stdc++.h> using namespace std; const int maxn=4e5+5; int n,m,k,cnt; //cnt表示连通块的数量 bool exist[maxn]; //exist[i]=1表示星球i目前存在（没有被摧毁） int fa[maxn],ans[maxn]; vector<int> v[maxn],atk; //v[x]存与x直接相连的点,atk存被摧毁的点 int find(int x) {return fa[x]<0 ? x : fa[x]=find(fa[x]);} inline void unite(int r1,int r2) { fa[r1]<fa[r2] ? fa[r1]+=fa[r2],fa[r2]=r1 : (fa[r2]+=fa[r1],fa[r1]=r2); } int main() { scanf("%d%d",&n,&m); memset(fa,-1,sizeof(fa)); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); v[x].push_back(y),v[y].push_back(x); } scanf("%d",&k); cnt=n-k; //最后的局面中，共有n-k个点，若不考虑边，则有n-k个连通块 for(int i=0;i<n;i++) exist[i]=1; for(int i=1;i<=k;i++) {int t; scanf("%d",&t); exist[t]=0,atk.push_back(t);} for(int i=0;i<n;i++) { if(!exist[i]) continue; for(int j=0;j<v[i].size();j++) { if(!exist[v[i][j]]) continue; int r1=find(i),r2=find(v[i][j]); if(r1!=r2) unite(r1,r2),cnt--; } } for(int i=k-1;i>=0;i--) { int x=atk[i]; ans[i]=cnt,exist[x]=1,cnt++; //注意：多加一个点，就多了一个连通块 for(int j=0;j<v[x].size();j++) { if(!exist[v[x][j]]) continue; int r1=find(x),r2=find(v[x][j]); if(r1!=r2) unite(r1,r2),cnt--; } } printf("%d\n",cnt); for(int i=0;i<k;i++) printf("%d\n",ans[i]); return 0; } |