题解 | #F题#

看结果，所有点都能在一起，那么它们都能同时在图上任意一个位置集合。 给图黑白染色，如果k个点颜色相同显然YES，当图中存在奇环时，也是YES，因为每个点可以走一圈奇环，改变当前的颜色。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<deque>
#include <time.h>
#include<unordered_map>
#include <set>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define all(v) v.begin(),v.end()
#define AC return 0
#define pb(v) push_back(v) 
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x3f3f3f3f
#define int long long
#define pii pair<int ,int > 
#define fi first
#define se second
#define endl "\n"
const int N=2e5+10;
const int mod=19650827;
int n,m,k;
int col[N];
int a[N];
vector<int > G[N];
int cir;
void dfs(int x ,int fa ,int co)
{
    col[x] = co;
   // cout<<" x "<<x<<" "<<co<<" "<<fa<<endl;
    for(int y:G[x])
    {
        if( y==fa ) continue;
       // cout<<" y "<<y<<endl;
        if( col[y]!=-1 )
        {
            if( co==col[y] ) cir=1;
            return;
        }
        dfs(y,x,co^1);
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
   freopen("in.txt", "r", stdin);
#endif  
   IOS;
    cin>>n>>m>>k;
    _for(i,1,m)
    {
        int x,y;cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    _for(i,1,n) col[i]=-1;
    _for(i,1,k) cin>>a[i];
    dfs(1,0,1);
    if( cir )
    {
        cout<<"YES"<<endl;
    }
    else 
    {
        int ok=1;
        _for(i,1,k)
        {
            if( col[a[i]]!=col[a[1]] )
            {
                ok=0;
                break;
            }
        }
       // _for(i,1,k) cout<<a[i]<<" ";
       // cout<<endl;
        if( ok ) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    AC;
}