图的m着色问题
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
输入格式
第1行有3个整数n、k和m,表示给定的图G有n个顶点、K条边、m种颜色,顶点的编号为1、2、3、4.....n。在接下来的k行种每行有两个整数u、v,表示图G的一条边(u,v)。
输出格式
程序运行结束时将计算出的不同着色方案数输出。如果不能着色,则程序输出-1。
样例
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
48