本文主要是介绍193 - Graph Coloring（DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：193 - Graph Coloring
题目大意：给出一个图，图里面有点和边，要求相邻的点不可以都是黑色的，问怎样上色黑色的点最多的，给出字典序最大的那种组合情况。
解题思路：dfs每个点是黑是白，将黑的点保存记录下来，然后下次再试探某个点是黑点的时候，就看看这个点和之前的那些点有没有相邻，相邻就表示这个点不是黑点。每个试探的点只需要是这个点之后的点就可以了，因为前面的点已经试探过了。
代码：
#include <stdio.h>
#include <string.h>const int N = 105;
int n, m, s[N][N], ans[N], cas, count, vis[N];bool judge (int x, int num) {for (int i = 1; i <= num; i++)if (s[x][vis[i]])return 1;return 0;
}void solve (int num, int x) {vis[num] = x;for (int i = x + 1; i <= n; i++) {if (judge (i, num))continue;solve (num + 1, i);}if (num >= count) {count = num;memcpy (ans, vis, sizeof (vis));}
}int main () {scanf ("%d", &cas);while (cas--) {scanf ("%d%d", &n, &m);memset (s, 0, sizeof(s));count = -1;int x, y;for (int i = 0; i < m; i++) {scanf ("%d%d", &x, &y);s[x][y] = s[y][x] = 1;}for (int i = 1; i <= n; i++) {memset (vis, 0, sizeof (vis));solve (1, i);}printf ("%d\n", count);for (int i = 1; i < count; i++)printf ("%d ", ans[i]);printf ("%d\n", ans[count]);}return 0;
}
这篇关于193 - Graph Coloring（DFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
