Graph Coloring
题意翻译
# 题目描述
请您编写一个程序找到一个给定图的最优染色方案。染色是指对图上的点染色,并且只有黑白二色可用。最优染色方案要求染成黑色的点最多。染色限制:禁止由一条边相连的两个点都染黑色。
# 输入格式
给定的图由点和无向边构成。点用1...n, n<=100来表示。无向边用两个顶点来表示,这两个顶点不会相同。
输入数据有m个图。第1行给出m。每个图的第一行给出两个数字n和k,分别指点数和边数。接下来的k行包含k条边的两个顶点,两个数字之间以空格相间。
# 输出格式
输出包含2m行,输入的每个图对应2行。每个图的第1行输出最大染黑点数,第2行输出一种可能的最优染色方案,即输出所有染黑的点,每两个点间以空格相间。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=129
[PDF](https://uva.onlinejudge.org/external/1/p193.pdf)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA193/550b3f8acbbc4c45392549d84ebc7e29e59b9428.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA193/e3f776deecdfe7122d51b6ad56a5a707e3aeea62.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA193/d2a5c463a32441e09bfb1f61731564a0170b199b.png)
输入输出样例
输入样例 #1
1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
输出样例 #1
3
1 4 5