牛客手速月赛43 F

题目 题意: 给出 n 个点 m 条边 的无向图，给出 k 个点，这 k 个点上每个点都有一个人，每个人每回合能走到一个相邻的节点（不能停留不走），问：有没有可能在某一个回合，让这些人都集中在一个点？(保证给出的k个点互不相同) 思路: 当时也没想明白，就感觉是两两之间的距离需要是偶数。因为两点移动只会使得二者的距离+2,0,-2，如果距离奇数是没法最后走到一起的。因此，可以bfs求最短路。但是有环，我就寄了。事后看了题解，不是用bfs求最短路，而是求是否有偶数路径。明显的二分图看不出来，有点捞. 思路一: 从k个点中任意一个开始bfs，判断是否其他点到该点都有偶数路径。 思路二: 二分图染色。对图进行黑白染色，如果这k个点都是同一颜色，同一颜色两两之间相距偶数条边，说明有解。(如果有奇环，可以通过奇环改变自己的奇偶性，必定有解。原来走一步到的点，现在可以走两步到。) 时间复杂度: O(n+m) 代码: 染色法

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i