牛客小白月赛43

F - 全体集合

https://ac.nowcoder.com/acm/contest/11220/F

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给出 $n$ 个点 $m$ 条边 的无向图，给出 $k$ 个点，这 $k$ 个点上每个点都有一个人，每个人每回合能走到一个相邻的节点（不能停留不走），问：有没有可能在某一个回合，让这些人都集中在一个点？

输入描述:

第一行包含三个整数 $n$ $m$ $k$ ，$1\le n,k\le 2e5$，$0\le m\le min(5e5,n*(n-1)/2)$。

接下来 $m$ 行，每行包括两个整数 $u$ $v$，表示存在一条从节点 $u$ 到 $v$ 的边，节点编号从 $1$ 开始，保证图联通，无重边，无自环。

接下来一行，包含 $k$ 个整数，分别表示有人所在的节点，保证 $k$ 个节点各不相同。

输出描述:

输出包括一行，如果有办法能让全部人都集中在一个点，输出”YES“，否则输出”NO“，不包含引号。

示例1

输入

3 2 2
1 2
2 3
1 3

输出

YES

说明

第一回合，让节点 $1$ 的人走到节点 $2$，节点 $3$ 的人走到节点 $2$ ，全都集中了，输出YES。

示例2

输入

3 2 2
1 2
2 3
1 2

输出

NO

说明

由于每回合不能不移动，不存在一种走法让全部人集中。

我的笔记

分析

问题转化

容易发现，如果每个人之间的路程长度为偶数，那么所有人一定可以集中到一起。距离近的人集中后，可以“左右横跳”来等剩下的人集中，因为每个人距离是偶数，左右横跳需要 2 步，所以可以保证所有人都集中到一起。如果有两个人之间的路程长度为奇数，那么他们将无法集中。因为“反复横跳”后，这两个人总是隔着一个距离，没法集中到一起。

所以题目问题就转化为：判断所有人两两之间是否都有偶数路径。还可进一步处理为：随意选择一个人，他和其他人是否都有偶数路径。

需要注意，两个人之间可以既存在奇数路程，也存在偶数路程，因为图可以连接成网，选取不同的路径，路程长度可以不同。

算法选择

可以先随意选择一个人（源码中选择的是第一个人），然后用 BFS 将这个人与每个节点的路径种类（即，是否有偶数路径、技术路径）计算出来，最后遍历一遍有人的节点是否都有偶数路径即可。

注意点

这一题 BFS 的子节点比较特殊，并不是直接为节点序号。因为我们既要计算是否有偶数路径，也要计算是否有奇数路径，这样才能用 BFS ，即：上一个有奇数路径，这一个就有偶数路径；上一个有偶数路径，这一个就有奇数路径。

因此子节点用了一个二元组表示，每个节点序号包含两个子节点，一个用来判断奇数路径，一个用来判断偶数路径。父子节点的递推就是，若父节点判断的是奇数（偶数）路径，子节点就是判断所有与父节点连接的点的偶数（奇数）路径情况。

源码

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
vector<int> connect[200010];
vector<int> people;
bool dis[200010][2];
queue<int> que;

void bfs(void)
{
    queue<pair<int, bool>> que;
    que.push({people[0], 0});
    while (!que.empty())
    {
        pair<int, bool> now = que.front();
        que.pop();
        for (int i = 0; i < connect[now.first].size(); i++)
        {
            pair<int, bool> next = {connect[now.first][i], now.second ? 0 : 1};
            if (!dis[next.first][next.second])
            {
                dis[next.first][next.second] = 1;
                que.push({next.first, next.second});
            }
        }
    }
}

int main(void)
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        connect[u].push_back(v);
        connect[v].push_back(u);
    }
    for (int i = 0; i < k; i++)
    {
        int t;
        scanf("%d", &t);
        people.push_back(t);
    }
    bfs();
    bool flag = true;
    for (int i = 0; i < people.size(); i++)
    {
        if (!dis[people[i]][0])
        {
            flag = false;
            break;
        }
    }
    if (flag)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}