题解 | #满意的数字#

F.

使用二分图进行分类讨论

1.如果不是二分图,那么一定是可以通过走染色不了的位置最终到一个结点

2.如果是二分图,那么就需要所有的结点都在一个同一个颜色的结点才有可能走到同一个结点,因为假设有一个人在黑色结点,那么下一步一定会是白色结点.那么他们永远不可能走到同一个色的结点

赛中没想到二分图QAQ,这么明显没想到

Code:

#include<bits/stdc++.h>
using namespace std;
vector<int> edge[200005];
int color[200005];
int n,m,k;
int num[200005];
bool flag;
void dfs(int x,int c){
    if(flag)    return;
    color[x] = c;
    int cc = 3 - c;
    for(int i = 0;i<edge[x].size();++i)
    {
        int v = edge[x][i];
        if(color[v]&&color[v]!=cc)
        {
            flag = true;
            return;
        }
        if(color[v])    continue;
        dfs(v,cc);
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i = 1;i<=m;++i){
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for(int i =1;i<=k;++i)
        cin>>num[i];
    dfs(1,1);
    if(flag)    cout<<"YES"<<endl;
    else{
        int cc = color[num[1]];
        for(int i = 2;i<=k;++i)
           if(color[num[i]]!=cc){
               cout<<"NO"<<endl;
               return 0;
            }
         cout<<"YES"<<endl;
    }
    return 0;
}