PTA刷题实战：图着色问题（C++邻接表+集合判重）保姆级代码解析

PTA刷题实战图着色问题C邻接表集合判重保姆级代码解析最近在PTA刷题时遇到一道经典的图着色问题题目要求判断给定的颜色分配方案是否满足图着色问题的解。这道题看似简单但实现过程中有不少细节需要注意。今天我就来分享一下我的解题思路和代码实现希望能帮助到正在准备PAT/PTA考试或算法竞赛的朋友们。1. 问题分析与数据结构选择图着色问题的核心在于判断相邻顶点是否颜色相同。首先我们需要明确题目要求给定无向图G(V,E)判断给定的颜色分配方案是否满足使用的颜色数量恰好为K种任意两个相邻顶点颜色不同对于数据结构的选择邻接表是最适合表示稀疏图的结构。相比邻接矩阵邻接表在空间复杂度上更有优势O(VE) vs O(V²)特别适合顶点数较多但边数相对较少的图。vectorint g[1010]; // 邻接表存储图结构这里我选择使用vector数组来构建邻接表因为动态数组方便添加边随机访问效率高内存管理由STL自动处理2. 输入处理与图构建题目输入分为几个部分顶点数V、边数E和颜色数KE条边的信息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容器可以方便地统计不同颜色的数量setint 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自动去重统计边界条件处理不当如K1时所有顶点必须同色但不相邻解决方法单独测试极端情况调试时可以添加临时输出语句检查中间结果// 调试输出邻接表 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中注释会增加代码长度完整代码实现时建议先写无注释版本通过测试再添加必要注释。对于竞赛和考试熟练度比完美注释更重要。