1.实现二分图的判定

怎么判断一个图是否是二分图呢?其实很简单。

  1. 对于一个图,我们任意选中图中一个未被选中过的点(默认为未被选中过),标记为选中过了,加入到处理队列中。然后枚举它相邻的所有点。
  2. 如果当前枚举的点未被选中过,则把当前枚举的点标记为与当前选中的点不一样的颜色,标记为选中过了,然后加入到处理队列中。
  3. 如果当前枚举的点被选中过了且颜色与当前选中的点颜色不同,则跳过当前枚举的点。
  4. 如果当前枚举的点被选中过了且颜色与当前选中的点颜色相同,则说明这个图不是二分图(得到答案),结束程序。
  5. 如果与当前选中的点相邻的点都已经被选中过了,而且没有发现颜色与当前选中的点颜色相同的,则从处理队列中去掉当前选中的点(pop操作)。
  6. 如果队列为空且所有的点都被选中过了,则说明这个图是二分图(得到答案),结束程序。
  7. 如果当前队列不为空,则选中处理队列中的第一个点,重新执行第二步。

整个过程用BFS实现,简单流程而自然~

2.模板题以及题解

HDU-1121:传送门
思路:模板题,判断是否是二分图,是就输出Correct,否则输出Wrong。

代码: