分两步:
1.判断连通性
2.判断所在连通分量是否是二分图
yes/no的判断:
1:不在一个连通分量,no
2.所在连通分量不是二分图,yes
3.机器人分布在二分图的两侧,no
4.分布在同侧,yes
依据:
如果给定的点中两点之间存在一条长度为偶数的迹,我们就可以选取某个点为终点,机器人可以沿着这条迹到达终点,先到的机器人随便找个点做往返,这样当最后一个机器人到达我们的终点时,机器人都在一个点上.
如果存在一个点,这个点与所有给定的点之间都有一条长度为t的迹,那么任两个给定的点之间都有长度为偶数的迹.
从而是等价转换.
只考虑图连通:
如果我们的图不是二分图,那么就有奇圈,这样,图中任两点之间都可以依靠这个奇圈存在一条长度为偶数的迹.
如果是二分图,那么同侧点之间才有偶迹,从而问题可解,速度很快.