题意

本题的目标是为给定的图找出一种最优着色方案。着色规则如下：

1.图的节点只能使用黑色和白色进行着色。

2.相邻节点不能同时为黑色。

3.最优着色方案是使图中黑色节点数量最多的方案。

输入包含多个图的信息，先给出图的数量 m。对于每个图，先给出节点数 n 和边数 k，接着的 k 行给出无向边的节点对。输出要为每个图输出两行，第一行是该图中能着黑色的最大节点数，第二行是一种可能的最优着色方案（列出黑色节点编号）。

解题思路

可以使用回溯法来解决此问题。回溯法是一种通过尝试所有可能的着色组合，找出满足条件的最优解的方法。具体步骤如下：

1.图的表示：使用邻接矩阵来表示图，方便判断两个节点是否相邻。

2.回溯搜索：从第一个节点开始，尝试将其着为黑色或白色，然后递归地处理下一个节点。在着色过程中，检查是否满足相邻节点不能同时为黑色的条件。

3.记录最优解：在搜索过程中，记录黑色节点数量最多的着色方案。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int n, k;
bool graph[MAXN][MAXN];
bool color[MAXN];
bool bestColor[MAXN];
int maxBlack = 0;

// 检查当前节点能否着黑色
bool canColorBlack(int node) {
    for (int i = 1; i <= n; ++i) {
        if (graph[node][i] && color[i]) {
            return false;
        }
    }
    return true;
}

// 回溯搜索
void backtrack(int node, int blackCount) {
    if (node > n) {
        if (blackCount > maxBlack) {
            maxBlack = blackCount;
            copy(color + 1, color + n + 1, bestColor + 1);
        }
        return;
    }

    // 尝试将当前节点着为黑色
    if (canColorBlack(node)) {
        color[node] = true;
        backtrack(node + 1, blackCount + 1);
        color[node] = false;
    }

    // 尝试将当前节点着为白色
    backtrack(node + 1, blackCount);
}

int main() {
    int m;
    cin >> m;

    while (m--) {
        cin >> n >> k;
        // 初始化图
        fill(&graph[0][0], &graph[0][0] + MAXN * MAXN, false);
        fill(color + 1, color + n + 1, false);
        fill(bestColor + 1, bestColor + n + 1, false);
        maxBlack = 0;

        // 读取边信息
        for (int i = 0; i < k; ++i) {
            int u, v;
            cin >> u >> v;
            graph[u][v] = graph[v][u] = true;
        }

        // 开始回溯搜索
        backtrack(1, 0);

        // 输出结果
        cout << maxBlack << endl;
        bool first = true;
        for (int i = 1; i <= n; ++i) {
            if (bestColor[i]) {
                if (!first) {
                    cout << " ";
                }
                cout << i;
                first = false;
            }
        }
        cout << endl;
    }

    return 0;
}