关闭农场Closing the Farm_Silver

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 int can[3001],n;
 8 int fa[3001];
 9 int ans[3001],a[3001];
10 int h[3001],ne[6001],to[6001],fr[6001],en=0;
11 inline void add(int a,int b)
12 {ne[en]=h[a];to[en]=b;fr[en]=a;h[a]=en++;}
13 inline int gf(int k)
14 {
15     if (fa[k]==k) return k;
16     else return fa[k]=gf(fa[k]);
17 }
18 int main()
19 {
20     memset(h,-1,sizeof h);
21     int n,m;
22     scanf("%d%d",&n,&m);
23     for (int i=1;i<=m;++i)
24     {
25         int a,b;
26         scanf("%d%d",&a,&b);
27         add(a,b);
28         add(b,a);
29     }
30     for (int i=1;i<=n;++i) scanf("%d",&a[i]),fa[i]=i;
31     for (int i=n;i>=1;--i)
32     {
33         can[a[i]]=1;
34         for (int j=h[a[i]];j>=0;j=ne[j])
35         {
36             if (can[fr[j]]&&can[to[j]])
37             {
38                 int l=fr[j],r=to[j];
39                 int fl=gf(l),fr=gf(r);
40                 if (fl!=fr) fa[fl]=fr;
41             }
42         }
43         int cnt=0;
44         for (int j=1;j<=n;++j)
45             if (can[j]&&fa[j]==j) cnt++;
46         if (cnt==1) ans[i]=1;
47     }
48     printf("YES\n");
49     for (int i=2;i<=n;++i) if (ans[i]) printf("YES\n");
50     else printf("NO\n");
51 }