首页 > 代码库 > BZOJ 4579: [Usaco2016 Open]Closing the Farm
BZOJ 4579: [Usaco2016 Open]Closing the Farm
Description
依次删去一个点和它的边,问当前图是否连通.
Sol
并查集.
倒着做就可以了.
每次将一个点及其的边加入,如果当前集合个数大于 1,那么就不连通.
Code
/************************************************************** Problem: 4579 User: BeiYu Language: C++ Result: Accepted Time:2196 ms Memory:10328 kb****************************************************************/ #include <cstdio>#include <vector>#include <iostream>using namespace std; const int N = 200050; int n,m,cs;int b[N],p[N],f[N],ans[N];vector< int > g[N]; inline int in(int x=0){ scanf("%d",&x);return x; }int find(int x){ return f[x] == x ? x : f[x]=find(f[x]); }int main(){ n=in(),m=in(); for(int i=1,u,v;i<=m;i++){ u=in(),v=in(); g[u].push_back(v),g[v].push_back(u); } for(int i=1;i<=n;i++) p[i]=in(); for(int i=1;i<=n;i++) f[i]=i; for(int x=n,u,v;x;--x){ cs++; u=p[x],b[u]=1; for(int i=0,lim=g[u].size();i<lim;i++){ v=g[u][i]; if(b[v]) if(find(u) != find(v)) f[find(u)]=find(v),cs--; } if(cs > 1) ans[x]=0;else ans[x]=1; } for(int i=1;i<=n;i++) if(ans[i]) puts("YES");else puts("NO"); return 0;}
BZOJ 4579: [Usaco2016 Open]Closing the Farm
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。