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;
}

  

上一篇:JAVA IO中的设计模式


下一篇:安卓手机与电脑无线传输文件(利用ftp服务)