首页 > 代码库 > BZOJ 1015 JSOI2008 星球大战 starwar 并查集
BZOJ 1015 JSOI2008 星球大战 starwar 并查集
题目大意:给定一个无向图,求联通块个数,以及k次每次摧毁一个点后的;联通块个数
将边和摧毁的点全记录下来,反着做即可。
注意被摧毁的点不能算作联通块
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 400400 using namespace std; struct abcd{ int to,next; }table[M]; int head[M],tot; int n,m,q; int fa[M],stack[M],destroy[M],top,now; bool destroyed[M]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } inline void Unite(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx==fy) return ; --now; fa[fy]=fx; } inline void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } int main() { int i,j,x,y; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); ++x;++y; Add(x,y); Add(y,x); } cin>>q; for(i=1;i<=q;i++) { scanf("%d",&destroy[i]); ++destroy[i]; destroyed[destroy[i]]=1; } now=n-q; for(j=1;j<=n;j++) if(!destroyed[j]) for(i=head[j];i;i=table[i].next) if(!destroyed[table[i].to]) Unite(j,table[i].to); stack[++top]=now; for(j=q;j;j--) { x=destroy[j]; destroyed[x]=0; ++now; for(i=head[x];i;i=table[i].next) if(!destroyed[table[i].to]) Unite(x,table[i].to); stack[++top]=now; } while(top) printf("%d\n",stack[top--]); }
BZOJ 1015 JSOI2008 星球大战 starwar 并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。