首页 > 代码库 > uva-10004-俩色图验证
uva-10004-俩色图验证
题意:
在1976年,四色猜想被一个计算机助手提出,这个理论表示对任意一个地图的上色都只需要四种
颜色,地图内每一个区块和相邻的区块颜色都不相同.
你现在被要求解决一个相似但相对简单的问题.给你任意一个连通的图你必须计算出这个图
是否能够被俩种颜色涂上颜色.意思就是如果一个结点被涂上颜色
(从一个只有俩种颜色的调色板中选取一个颜色),那么相邻的俩个结点都不能有相同的颜色.
为了使问题更加简单,我们保证一下条件.
1:结点不存在自己到自己的边(不存在结点1有条边到结点1)
2:是一个无向图,如果结点a有条边到结点b,可以假设结点b也有条路到结点a
3:是一个强联通图,意思就任意一个结点都有一条路到其他结点.
输入
输入由几组测试用例组成,每一组测试开始的第一行包含一个数字n(1<n<200),表示包含有n个结点.
第二行包含边的数目L,随后L行,每一行包含俩个数字,表示这俩个结点之间有一条边相连接,
图的一个结点使用a标识(0<=a<n),n=0表示输入结束,不用处理.
输出
看输出用例
uva-10004-俩色图验证
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。