有JAVA编写着色问题
问题描述:对于给定的图G,如果存在一种用2种颜色对顶点着色的方案,使得图中任意一条边所
连接的2 个顶点着有不同颜色,则称图G 是可2着色的。
.编程任务:
对于给定的图G,编程计算图G 是否可2 着色的。
.数据输入:
由文件input.txt 给出输入数据。第1 行有2 个正整数n 和m,表示给定的图G 有n 个
顶点和m条边,顶点编号为1,2,…,n。接下来的m行中,每行有2 个正整数u,v,表示
图G 的一条边(u,v)。
.结果输出:
将编程计算出的图G 的2 着色性输出到文件output.txt。如果图G 不是可2 着色的,则
输出“No”;如果图G 是可以2 着色的,则输出“Yes”,并输出一种2 着色方案。
输入文件示例 输出文件示例
input.txt output.txt
8 7 Yes
1 3 1 1 0 0 1 0 1 0
1 6
2 8
3 7
4 5
5 6
5 8
谁有好的代码不,或说说思路 --------------------编程问答-------------------- 有点不理解了,两个正整数如何构成一条边?(u,v)
暂且先抛开你所解释的,我的想法是直接将几个顶点初始化为0,然后任选一个顶点设为1,开始递归遍历与之连接的点,如果其值为0则设为2,如果其值等于所选点的值(1)则表明没法着色,如果为2则返回。表达不是很清楚哈。就是说找一个顶点A相连的所有点,如果这些点的值与这个顶点A的未赋值,则赋值与顶点A不同的值;如果相同则表明不能着色,否则就是已经遍历过的点。这样就完成一次调度,然后再把刚遍历的点再递归这样调度一次,赋值为顶点A的值,不知道解释清楚没? --------------------编程问答-------------------- u和v分别代表的是各个顶点的序号,你的解释有点不懂啊,我的思路是,把input.txt中左边一列序号的点设置为0,右边的设置为1,查找和各个点相连接的点,如果数值相同,则设为两相反直,但不知道该怎么结束,怎么才能判断是不可2着色的图。你能不把代码写下看下。
补充:Java , Java SE