当前位置：首页 > news >正文

UVa 193 Graph Coloring

news 2026/5/10 10:43:47

题目分析

题目要求对一个无向图进行黑白染色，使得相邻节点不能同时为黑色，并且黑色节点的数量最大化。图的大小为n≤100n \leq 100n≤100，需要输出最大黑色节点数以及一种可行的方案。

由于nnn最大为100100100，暴力枚举所有2n2^n2n种情况不可行。但题目中图的边数没有明确上界，在UVa OJ\texttt{UVa OJ}UVa OJ的测试数据中，回溯法足以通过。

解题思路

采用DFS\texttt{DFS}DFS回溯法，按节点编号从111到nnn依次决定每个节点是否染成黑色。

对于当前节点node，有两种选择：

尝试染成黑色：要求当前节点与之前已染成黑色的节点都不相邻。如果满足条件，就将其染黑并递归到下一个节点。
不染成黑色：直接递归到下一个节点。

当递归到n+1n + 1n+1时，说明所有节点都已处理完毕，此时统计黑色节点数量，如果比当前最优解更大，则更新最优解并记录方案。

正确性说明

该回溯算法实际上搜索了所有可能的合法染色方案。由于每次染黑前都会检查与已有黑节点的邻接关系，保证了方案的有效性。在叶子节点处更新最优解，因此最终得到的必然是最大黑色节点数。

复杂度分析

最坏情况下的时间复杂度为O(2n)O(2^n)O(2n)，但由于剪枝（只有当节点不与任何黑节点相邻时才尝试染黑），实际运行效率远高于理论最坏情况。对于 UVa 的测试数据，该算法可以快速通过。

代码实现

// Graph Coloring// UVa ID: 193// Verdict: Accepted// Submission Date: 2016-03-16// UVa Run Time: 0.003s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net//#include<bits/stdc++.h>usingnamespacestd;vector<vector<int>>edges;// 邻接表，存储无向图vector<bool>black;// 标记节点是否染成黑色vector<int>answer;// 存储最优解中的黑色节点列表intmaximum,n;// maximum 为最大黑色节点数，n 为节点数// 深度优先搜索回溯// node 表示当前处理的节点编号（从 1 开始）voidbacktrack(intnode){// 所有节点处理完毕if(node==n+1){// 统计当前方案中的黑色节点数inttotal=0;for(inti=1;i<=n;i++)if(black[i])total++;// 更新最优解if(total>maximum){maximum=total;answer.clear();for(inti=1;i<=n;i++)if(black[i])answer.push_back(i);}return;}// 检查当前节点是否与某个已被染黑的节点相邻boolblacked=false;for(inti=0;i<edges[node].size();i++)if(black[edges[node][i]]){blacked=true;break;}// 如果相邻节点中没有黑色，则可以尝试将当前节点染成黑色if(blacked==false){black[node]=true;// 染黑backtrack(node+1);// 处理下一个节点black[node]=false;// 回溯，恢复状态}// 将当前节点保持白色，继续搜索backtrack(node+1);}// 求解当前图的最优染色方案并输出结果voidfindMaximum(){maximum=0;black.resize(n+1);fill(black.begin(),black.end(),false);backtrack(1);// 从节点 1 开始搜索// 输出最大黑色节点数cout<<maximum<<"\n";// 输出一种最优染色方案中的黑色节点列表for(inti=0;i<answer.size();i++)cout<<(i>0?" ":"")<<answer[i];cout<<"\n";}intmain(){intm,k,start,end;cin>>m;// 读取测试用例个数while(m--){cin>>n>>k;// 读取节点数 n 和边数 k// 初始化邻接表（1-based 索引）edges.clear();edges.resize(n+1);// 读入 k 条边，构建无向图for(inti=1;i<=k;i++){cin>>start>>end;edges[start].push_back(end);edges[end].push_back(start);}findMaximum();// 求解并输出结果}return0;}