首页 > 代码库 > 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