111qqz的小窝

老年咸鱼冲锋!

uva 10004 Bicoloring (交叉染色法判断二分图模板题)

uva10004题目链接

题意:给出一个无向图,问是否可以组成二分图。

思路:交叉染色法。

首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:

          1.未染色    那么继续染色此节点(染色为另一种颜色)

          2.已染色但和当前节点颜色不同      跳过该点

          3.已染色并且和当前节点颜色相同       返回失败(该图不是二分图)

 

学习链接

 

upd:更正dfs中的一个错误。

把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false;

之前的写法中,当前层之后的层的没有起到任何作用。。。

而实际上应该是后面只要某一层不满足,整体就该为false.

写成这样这题还能过我也是醉了。。。。

说点什么

您将是第一位评论人!

提醒
wpDiscuz