题解 | #全体集合#

Problem

Solution

分情况讨论，是二分图、不是二分图。
非二分图： 则代表一定存在一个奇数点位能让所有人都在一起。
二分图： 则需要判断每个人的是否被染成同一个颜色，是则可以集中在一个点，不是则不能。

前几天代码上传错了 抱歉抱歉~

Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int N = 2e5 + 7, M = 2e6 + 7;
 
int h[N], e[M], ne[M], idx, n, m, k;
int color[N];
int num[N];
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
bool dfs(int u, int c)
{
    color[u] = c;
 
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j])  // 判断有没有被染过色
        {
            if (!dfs(j, 3 - c)) return false; 
        }
        else if (color[j] == c) return false;  // 一条边上的两个点颜色相等，返回false
    }
 
    return true;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
 
    while (m--)
    {
        int x, y, z;
        cin >> x >> y;
        add(x, y), add(y, x);
    }
     
    for (int i = 1; i <= k; i++)
    {
        cin >> num[i];
    }
 
    bool f = true;
    for (int i = 1; i <= n; i++)  // 给所有的点染色
    {
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                f = false;
                break;
            }
        }
    }
 
    if (!f) cout << "YES";
    else
    {
        bool c = true;
        int a = color[num[1]];
        for (int i = 2; i <= k; i++)
        {
            if (a != color[num[i]])
            {
                c = false;
                break;
            }
        }
        if (c) cout << "YES";
        else cout << "NO";
    }
    return 0;
}