BZOJ2338/HNOI2010/Planar

Posted on By 二价氢

#题目描述

#做法

我们有一条哈密顿回路()

将它们画在一条坐标轴上

然后,用题目中给的图中的边覆盖这个坐标轴

枚举,如果发现冲突则在冲突的两条边上连边(将原图的边当成点)

因为一条边要么在回路内部,要么在回路外部,所以,满足题意的平面图一定是二分图

二分图染色判断即可

#复杂度分析

二分图的染色判断为

#AC Code