#include <iostream> #include <vector> using namespace std; const int MAXN = 100; int n, m; int color[MAXN]; // 记录每个节点的颜色 bool g[MAXN][MAXN]; // 邻接矩阵 vector<int> adj[MAXN]; // 邻接表 void dfs(int u, int c) { color[u] = c; for (int v : adj[u]) { if (color[v] == 0) { // 如果未被染色，染成另一种颜色 dfs(v, 3 - c); } else if (color[v] == c) { // 如果相邻节点颜色相同，无法着色 cout << "Impossible to color the graph with " << m << " colors." << endl; exit(0); } } } int main() { // 读入邻接矩阵 cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> g[i][j]; if (g[i][j]) { adj[i].push_back(j); } } } // 深度优先搜索染色 m = 1; for (int u = 1; u <= n; u++) { if (color[u] == 0) { dfs(u, 1); m = max(m, color[u]); } } // 输出结果 cout << "The graph can be colored with " << m << " colors." << endl; cout << "Coloring result: "; for (int u = 1; u <= n; u++) { cout << color[u] << " "; } cout << endl; return 0; }图图着色

这段代码实现了图的着色，采用了深度优先搜索的方法。在搜索过程中，用颜色数组记录每个节点的颜色，初始值为0。如果一个节点未被染色，就将它染成另一种颜色（用1和2代表两种颜色），然后继续对它的邻居节点进行染色。如果一个节点已经被染色，并且它的颜色与相邻节点的颜色相同，说明无法用m种颜色对该图进行着色。最后输出着色结果和需要的最少颜色数。

该算法的时间复杂度为O(n^2)，其中n为节点数。实际上，采用邻接表存储图的话，时间复杂度可以降为O(n+m)，其中m为边数。