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

目录

• $code$

---

题目

p3144 [usaco16open]关闭农场closing the farm_silver

思路

先全部读入利用并查集倒着处理

$code$

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#define maxn 3001
using namespace std;
int n,m;
bool vis[maxn];
int fa[maxn],r[maxn],ans[maxn];
int u[maxn],v[maxn],del[maxn];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void union(int x,int y){
    int rootx=find(x),rooty=find(y);
    if(rootx==rooty) return;
    if(r[rooty]>r[rootx]) fa[rootx]=rooty;
    else if(r[rootx]>r[rooty]) fa[rooty]=rootx;
    else{
        fa[rooty]=rootx;
        r[rootx]++;
    }
}
inline void read(int &t){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    t=f?-x:x;
}

int main(){
    read(n),read(m);
    for(int i=1;i<=m;++i) read(u[i]),read(v[i]);
    for(int i=1;i<=n;++i) read(del[i]),fa[i]=i;
    for(int i=n;i>0;--i){
        vis[del[i]]=1;
        for(int j=1;j<=m;++j){
            if(vis[u[j]]&&vis[v[j]]){
                union(u[j],v[j]);
            }
        }
        for(int j=1;j<=n;++j){
            if(vis[j]&&find(j)==j){
                ans[i]++;
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(ans[i]==1) puts("yes");
        else puts("no");
    }
    return 0;
}