题意：图上的点染色，给出的边的两个点不能都染成黑色，问最多可以染多少黑色。
很水的一题，用dfs回溯即可。先判断和当前点相连的点是否染成黑色，看这一点是否能染黑色，能染色就分染成黑色和白色两种情况递归，如果不能就单递归白色。
代码：
#include <cstdio>
#include <cstring>
const int maxn = 110;
int cas, v, e, M;
bool g[maxn][maxn];
int color[maxn], rec[maxn]; void dfs(int p, int black) {
if (p > v) {
if (M < black) {
M = black;
for (int i = 1; i <= v; i++)
rec[i] = color[i];
}
return;
}
//judge if can color
for (int i = 1; i <= v; i++)
if (g[p][i] && color[i]) {
dfs(p + 1, black); //can't color black, color white and return
return;
}
color[p] = 1;
dfs(p + 1, black + 1); //can color black
color[p] = 0;
dfs(p + 1, black); //can color white
} int main() {
scanf("%d", &cas);
while (cas--) {
M = 0;
scanf("%d%d", &v, &e);
memset(g, 0, sizeof(g));
for (int i = 0; i < e; i++) {
int a, b;
scanf("%d%d", &a, &b);
g[a][b] = g[b][a] = 1;
}
dfs(1, 0);
printf("%d\n", M);
int cnt = 0;
for (int i = 1; i <= v; i++)
if (rec[i]) {
if (++cnt != M)
printf("%d ", i);
else
printf("%d\n", i);
}
}
return 0;
}
Input：
4 5 0 8 4
1 2
3 4
5 6
6 8 2 1
1 2 20 19
1 10
2 5
3 4
4 9
5 17
6 4
8 19
9 13
10 11
11 14
12 1
13 6
14 3
15 4
16 5
17 8
18 9
19 15
20 4
Output：
5
1 2 3 4 5
5
2 4 5 7 8
1
2
11
1 2 3 6 7 8 9 11 15 16 20