PTA刷题实战：图着色问题（C++邻接表+集合判重）保姆级代码解析
最近在PTA刷题时遇到一道经典的图着色问题，题目要求判断给定的颜色分配方案是否满足图着色问题的解。这道题看似简单，但实现过程中有不少细节需要注意。今天我就来分享一下我的解题思路和代码实现，希望能帮助到正在准备PAT/PTA考试或算法竞赛的朋友们。
1. 问题分析与数据结构选择
图着色问题的核心在于判断相邻顶点是否颜色相同。首先我们需要明确题目要求：
- 给定无向图G=(V,E)
- 判断给定的颜色分配方案是否满足：
- 使用的颜色数量恰好为K种
- 任意两个相邻顶点颜色不同
对于数据结构的选择，邻接表是最适合表示稀疏图的结构。相比邻接矩阵，邻接表在空间复杂度上更有优势（O(V+E) vs O(V²)），特别适合顶点数较多但边数相对较少的图。
vector<int> g[1010]; // 邻接表存储图结构这里我选择使用vector数组来构建邻接表，因为：
- 动态数组方便添加边
- 随机访问效率高
- 内存管理由STL自动处理
2. 输入处理与图构建
题目输入分为几个部分：
- 顶点数V、边数E和颜色数K
- E条边的信息
- N个待检查的颜色分配方案
int v, e, k; cin >> v >> e >> k; // 构建邻接表 for (int i = 1; i <= e; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); // 无向图需要双向添加 }注意：无向图的边需要在邻接表中双向添加，即如果顶点A与B相连，既要在A的邻接表中添加B，也要在B的邻接表中添加A。
3. 颜色分配方案检查
对于每个颜色分配方案，我们需要进行两个主要检查：
3.1 颜色种类数检查
使用STL中的set容器可以方便地统计不同颜色的数量：
set<int> s; // 用于存储不同颜色 int c[1010]; // 存储每个顶点的颜色 // 读取颜色分配 for (int i = 1; i <= v; i++) { cin >> c[i]; s.insert(c[i]); } // 检查颜色数量 if (s.size() != k) { cout << "No\n"; continue; }set的insert操作会自动去重，size()方法直接返回不同颜色的数量，非常高效。
3.2 相邻顶点颜色检查
这是问题的核心检查部分，需要遍历每个顶点及其所有邻接点：
int f = 0; // 标记是否发现冲突 for (int i = 1; i <= v; i++) { for (int j = 0; j < g[i].size(); j++) { if (c[i] == c[g[i][j]]) { f = 1; break; } } if (f) break; }这里有几个优化点：
- 一旦发现冲突立即跳出循环，避免不必要的检查
- 外层循环从1到v，内层循环遍历每个顶点的邻接表
- 使用标记变量f来记录检查结果
4. 常见错误与调试技巧
在实现过程中，我遇到过几个典型的错误：
数组越界：顶点编号从1开始，但数组大小设置不足
- 解决方法：将数组大小设置为略大于最大顶点数(如1010)
邻接表构建错误：忘记无向图需要双向添加边
- 解决方法：添加边时同时处理g[x].push_back(y)和g[y].push_back(x)
颜色数量判断错误：直接统计颜色数组中的不同值
- 解决方法：使用set自动去重统计
边界条件处理不当：如K=1时所有顶点必须同色但不相邻
- 解决方法：单独测试极端情况
调试时可以添加临时输出语句检查中间结果：
// 调试输出邻接表 for (int i = 1; i <= v; i++) { cout << "顶点" << i << "的邻接点: "; for (int j = 0; j < g[i].size(); j++) { cout << g[i][j] << " "; } cout << endl; }5. 性能优化与代码风格
考虑到PTA的评判系统对时间和空间有限制，我们需要注意：
输入输出效率：使用cin/cout时，可以添加同步优化
ios::sync_with_stdio(false); cin.tie(0);循环优化：减少不必要的循环和条件判断
- 例如发现冲突后立即跳出多层循环
变量作用域：将只在循环内使用的变量声明在循环内部
- 如标记变量f可以在检查每个方案时重新声明
代码可读性：合理使用注释和空行分隔逻辑块
- 但注意PTA中注释会增加代码长度
完整代码实现时，建议先写无注释版本通过测试，再添加必要注释。对于竞赛和考试，熟练度比完美注释更重要。
