洛谷P3144 [USACO16OPEN]关闭农场Closing the Farm

农夫约翰和他的奶牛准备去旅行，所以约翰想要把他的农场临时关闭。

农场有N个牛棚（牛棚从1到N编号），有M条路连接这些牛棚(1≤N,M≤3000)。

约翰打算挨个关闭牛棚，在关牛棚的时候，

他突然想起一个有趣的问题：剩余的这些没有关闭的牛棚是不是连通呢？

连通指的是从任何一个牛棚出发，都能到达其他牛棚（注意：已经关闭的牛棚不可以通行）。

Input

第一行包括两个整数N M，

接下来M行，每行输入两个整数x y，表示x和y牛棚之间存在一条路，路是双向通行的。

接下来n行，表示关牛棚的顺序。

Output 输出N行：

第一行表示初始状态下，牛棚是否连通；

接下来N-1行，表示关闭对应牛棚后，剩余牛棚是否联通。

如果连通，输出YES，不连通，输出NO。（最后一次关闭不需要输出）。

————————————————————————————————————————

回来补一波并查集

这里我们做一波离线处理将删点转换为加点也就是将关闭变为开启

那么我们每次开启一个牛棚x k++（k指的是当前联通快的个数）

然后我们枚举x的所有出路找到已经开始的牛棚如果他们不在一个了联通块内k-- 合并两个块

最后如果这个时刻k是1 那么就是联通否则不是

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,f[M],h[M],usd[M];

int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

int first[M],cnt,c[M];

struct node{int to,next;}e[*M];

void ins(int a,int b){

    cnt++; e[cnt].to=b; e[cnt].next=first[a]; first[a]=cnt;

}

void insert(int a,int b){ins(a,b); ins(b,a);}

int main()

{

    int x,y;

    n=read(); m=read();

    for(int i=;i<=n;i++) f[i]=i;

    for(int i=;i<=m;i++) x=read(),y=read(),insert(x,y);

    for(int i=;i<=n;i++) c[i]=read();

    for(int i=n;i>=;i--){

        k++; usd[c[i]]=;

        int now=c[i],p=find(now);

        for(int j=first[now];j;j=e[j].next){

            if(!usd[e[j].to]) continue;

            int q=find(e[j].to);

            if(p==q) continue;

            f[q]=p; k--;

        }

        h[i]=k;

    }

    for(int i=;i<=n;i++)

        if(h[i]==) printf("YES\n");

        else printf("NO\n");

    return ;

}

巴特西

洛谷P3144 [USACO16OPEN]关闭农场Closing the Farm

最新文章

热门文章