题解 P3144 【[USACO16OPEN]关闭农场Closing the Farm_Silver】

Orion_Rigel · 2016-09-29 00:14:03 · 题解

看到楼上有了灌水判联通，我就写一个并查集好了。

可以倒着加入边，然后每次暴力的去找根的个数，如果大于1就是NO

储存起来倒序输出。

------完结，撒花-----

···

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int can[3001],n;
int fa[3001];
int ans[3001],a[3001];
int h[3001],ne[6001],to[6001],fr[6001],en=0;
inline void add(int a,int b)
{ne[en]=h[a];to[en]=b;fr[en]=a;h[a]=en++;}
inline int gf(int k)
{
    if (fa[k]==k) return k;
    else return fa[k]=gf(fa[k]);
}
int main()
{
    memset(h,-1,sizeof h);
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for (int i=1;i<=n;++i) scanf("%d",&a[i]),fa[i]=i;
    for (int i=n;i>=1;--i)
    {
        can[a[i]]=1;
        for (int j=h[a[i]];j>=0;j=ne[j])
        {
            if (can[fr[j]]&&can[to[j]])
            {
                int l=fr[j],r=to[j];
                int fl=gf(l),fr=gf(r);
                if (fl!=fr) fa[fl]=fr;
            }
        }
        int cnt=0;
        for (int j=1;j<=n;++j)
            if (can[j]&&fa[j]==j) cnt++;
        if (cnt==1) ans[i]=1;
    }
    printf("YES\n");
    for (int i=2;i<=n;++i) if (ans[i]) printf("YES\n");
    else printf("NO\n");
}
···