PTA图着色问题：验证而非求解，边数组与set高效实现

1. 题目到底想考什么从“NP完全”标签到三个验证条件看到“图着色问题”这五个字很多人本能地紧张起来毕竟图着色是图论里挂着“NP完全”标签的经典难题。但如果你真的打开PTA平台这道题把题面从头读一遍会发现它实际要你做的事非常“小”——题目没有让你去求一个图的最小着色数也没有让你判断是否存在某种合法着色方案而是反过来给定一个完整的着色方案让你判断这个方案是不是“图着色问题的一个解”。这个反转很关键。搜索空间巨大的构造问题一旦变成对给定答案的验证问题难度就断崖式下降。整道题的规则拆开来看只有三条每条边两端的顶点颜色必须不同。整个图实际使用到的颜色种类数必须恰好等于给出的K。每个顶点都必须被染色这一点输入格式天然保证。很多人第一遍读题时会把第二条漏掉或者读成“不超过K种”这就是这道题最大的失分点。题目里说的是“能否用K种颜色为V中的每一个顶点分配一种颜色”验证时也必须严格按“恰好K种”来判定。多一种少一种都不行这和“最少需要几种颜色”完全不是一个概念。再从输入输出格式看题目结构非常规整第一行给出顶点数V、边数E和颜色数K顶点编号从1到V接下来E行是边的两个端点然后是一个正整数N表示待检查的着色方案数量之后每行按顶点顺序给出V个颜色值。数据范围方面V不超过500N不超过20这意味着整体计算量非常小根本不需要什么高级优化。搞清楚这些之后你会发现这道题真正考察的其实是你读题的能力以及把文字规则翻译成代码逻辑的熟练度。算法本身连“图论算法”都算不上就是一个静态检查的模拟题更像是数据结构课上对“图存储方式”的一次基本功测试。2. 数据结构选型为什么我选择“边数组”而不是邻接表既然核心操作是“检查每条边的两个端点颜色是否相同”那存图方式就值得先想清楚。常见的存图方案无非三种邻接矩阵、邻接表、边数组。我先把它们的适用场景和优劣放在一起做个对比再解释为什么这道题选边数组最顺手。存储方式空间复杂度判断一条边是否冲突适用场景邻接矩阵O(V^2)500×500约250KB枚举所有边时需双层循环不够直接稠密图、需要快速查询任意两点是否有边邻接表O(VE)需遍历每个顶点的邻接点可能重复检查同一条边稀疏图、DFS/BFS遍历边数组O(E)每条边一对端点直接顺序遍历所有边天然不重复只关心边的集合不需要邻居关系如果选用邻接表需要遍历每个顶点的邻接点还要额外用一个visited标记来避免重复检查同一条无向边逻辑上绕了一圈。如果选用邻接矩阵虽然V只有500空间还是能扛住但判断阶段需要两层循环把所有点对扫一遍很多非连边也会被白扫一次浪费了计算量。边数组是最直接的表达把输入里的E条边原样存进一个vectorpairint,int判断时从头到尾扫一遍每条边恰好检查一次。代码里不会多出一层无关的逻辑也根本不需要担心重复或遗漏。用边数组还有另一个潜在优势即使E逼近最大可能值也就是完全图的边数约12.5万条每条边用一个8字节的pairint,int来存总空间也就在1MB上下完全不用操心内存限制。所以这道题选边数组不是因为别的方案不能用而是因为它和本题的验证式逻辑命中最准。 我也建议你在做题前养成一个习惯先看操作是什么再选数据结构。如果操作是“查某两个点之间有没有边”邻接矩阵或哈希表更好如果操作是“沿邻居遍历”邻接表更好如果操作是“遍历所有边做判定”边数组永远是最清爽的选择。把这一步想清楚代码写起来会顺很多。 ## 3. 核心判断逻辑set统计颜色数加边两端的判重 题目规则的代码化很简单但有几个容易写歪的地方。先看颜色种类的统计。每个顶点都会拿到一个整数颜色颜色编号的范围题目没有限制可能是正数、零甚至负数。如果你试图用数组下标来统计颜色出现次数那遇到负数直接越界就算颜色范围刚好避开负数也要先遍历找出颜色最大值再开数组麻烦且脆弱。 最稳妥的做法是用标准库的set容器边读入颜色边插入最后直接取size()得到的就是这个方案实际用到的颜色种类数。V最多500插入500个元素set内部红黑树操作的log因子在这个规模下完全无感不值得为了省这点时间引入坐标压缩之类的复杂处理。 cpp vectorint color(v 1); setint used; for (int i 1; i v; i) { scanf(%d, color[i]); used.insert(color[i]); }拿到used.size()之后马上和K比较。如果两者不相等这个方案已经判死刑了直接输出No并continue后面的边就不用再扫了能省下一点无效计算。这个提前退出的小动作属于典型的“用规则剪枝”。颜色数检查通过之后再进入边的检查。遍历边数组判断每一条边的两个端点颜色是否相同。bool ok true; for (auto e : edges) { if (color[e.first] color[e.second]) { ok false; break; } }一旦发现冲突立刻break不再看后面的边。注意这里比较的是color[e.first]和color[e.second]下标不需要转换因为题目里顶点编号就是1到V与我们开数组时的偏移完全一致。整个流程总结下来就是三个阶段读颜色并统计种类数、判断种类数是否等于K、扫描所有边判断端点颜色是否冲突。两个判断一个有先后顺序先判种类数再判边冲突顺序不能乱。如果先扫边再判种类数也能得到同样的结论但你会多扫一遍边在N较大的时候白白浪费时间。这里的核心思路是“验证”而不是“求解”所以不需要DFS、不需要回溯、不需要剪枝搜索。你只需要把题目给的方案逐条对照规则任何一条规则被违反整个方案就不合法。把“验证规则”拆解清楚代码自然水到渠成。4. 完整AC代码与自测用例设计下面给出我在PTA平台上以C写的可直接提交版本代码力求直白注释标在关键位置。#include bits/stdc.h using namespace std; int main() { int v, e, k; scanf(%d %d %d, v, e, k); vectorpairint, int edges; edges.reserve(e); for (int i 0; i e; i) { int a, b; scanf(%d %d, a, b); edges.push_back({a, b}); } int n; scanf(%d, n); while (n--) { vectorint color(v 1); setint used; for (int i 1; i v; i) { scanf(%d, color[i]); used.insert(color[i]); } if ((int)used.size() ! k) { puts(No); continue; } bool ok true; for (auto e : edges) { if (color[e.first] color[e.second]) { ok false; break; } } puts(ok ? Yes : No); } return 0; }代码本身很短但有两个细节值得单独说。第一color数组开的是v1而不是v因为顶点编号从1开始这个“多开一格”的习惯能避免很多下标问题。第二scanf和puts搭配使用在数据量很小的时候cin/cout也完全跑得过但如果你的代码里混用cin和scanf且没有关闭同步某些评测环境可能表现异常建议统一使用一套输入输出方式。接下来给一组自测数据帮你验证自己写的代码逻辑是否完整。4 3 3 1 2 2 3 3 4 2 1 2 3 4 1 2 1 3第一个方案的内容是四个顶点颜色分别为1、2、3、4实际用了4种颜色而K是3因此会输出No。第二个方案颜色分别为1、2、1、3实际用色是1、2、3共3种恰好等于K同时三条边(1,2)、(2,3)、(3,4)的两端颜色都不相同所以输出Yes。这条用例的核心目的是确认你确实把“恰好K种”还是“不超过K种”分清了。再看一条负数颜色的用例。3 2 2 1 2 2 3 1 -1 0 -1三个顶点颜色为-1、0、-1实际用色两种恰好等于K。边(1,2)对比-1和0不同边(2,3)对比0和-1不同。所以答案是Yes。如果有人在统计颜色时用了数组下标-1这一关直接就过不去了很可能在本地莫名其妙报运行时错误。还有一条更极限的自测专门测试“颜色数不对时是否提前结束”。3 0 1 1 5 5 5图没有边三个顶点都用同一种颜色5实际用色1种等于K。因为没有边所以没有冲突输出Yes。这里注意E可以为0也就是空图务必保证代码能处理E等于0的情况否则边数组循环逻辑没问题但有人会忘记给edges做空判断导致后面遍历时行为异常。自测完之后可以顺手核算一下复杂度。每次查询要读V个颜色插入set然后检查E条边。V最大500E最大约12.45万N最大20总比较次数不超过250万外加set的log因子运行时间依然是毫秒级。空间方面边数组约1MBset临时对象每个查询几百字节所有开销都非常舒适。5. 复盘经典踩坑颜色编号是负数与“恰好K色”的隐藏条件代码写出来很简单但这道题在真正提交之前有几个坑会让人反复吃罚时。第一个坑就是前面反复强调的“恰好”属性。不少人的判断逻辑写成了used.size() k就输出Yes原因是他们潜意识里把K理解成一个“上限”觉得用色少于等于K是允许的。一旦这样写所有实际用色少于K的方案都会错误地输出Yes而PTA的强测试用例显然专门覆盖了这种情况结果就是本地样例全过提交全红。第二个坑是颜色编号可能为负数。这题跟很多着色题不一样它的颜色值并不是规定好的1到K之间的正整数而是任意整数。我见过有人用vector cnt(maxColor1)这种方式来统计颜色数先找最大颜色再开数组结果遇到负数直接崩溃。用set统计能够一劳永逸地避开这个问题不需要预先知道颜色值的范围也不需要坐标压缩。第三个坑是输出格式。题目要求的是Yes和No首字母大写后面小写。有人会输出YES或者NO还有人混用True和False在严格匹配输出的评测系统里这些全都会判错。这看起来是低级失误但在时间压力下很多人真的会犯尤其是从其它竞赛习惯切换过来时更容易写顺手。第四个坑和我刚提到的E0情况相关。有同学认为“没有边那肯定所有方案都是Yes”然后直接不读取颜色数据就开始输出结果整个程序输出顺序错乱。不管E是否为0每个查询的颜色数组都必须正常读入因为你要用它们来判断实际颜色种类数是否等于K。这一点在自测时容易被忽略但题目明确允许E等于0所以必须主动测一遍。还有一个隐蔽的小坑当used.size() ! k时部分人觉得“反正都是No”于是直接continue但之前已经把这一行的所有颜色读完了。这没问题。但如果你把提前判断写在了读完颜色之前那么输入流里会残留未消费的数据下一行方案读取全部错位。务必先完成一整行的颜色读取再做判断。这些坑本质上都源于读题不够细。颜色编号可以是负数说明出题人在刻意引导你用set或map要求恰好K种颜色说明出题人在提醒你区别“恰好”和“不超过”输出严格区分大小写说明这叫“细节决定成败”。做题的时候把这些读出来比着急写代码重要得多。6. 从这道题延伸出去验证问题、搜索问题与真实应用场景做完一道题如果不往深处想一想收获就会停留在“AC了”这个层面。图着色问题背后其实藏着一个很值得玩味的差异构造一个合法着色方案是NP难的验证一个给定着色方案却是多项式时间可解的。这两者之间的距离正是“解决问题”和“检查答案”之间的距离。你可以用生活场景来类比期末考试结束后老师批改一张已经完全填好的答题卡只需要对照标准答案逐项核对很快就能完成但如果让老师在一张空白答题卡上优化每一道题的作答顺序同时满足各种约束条件那就是另一码事了。PTA这道题恰恰把你放在“批改者”的位置上而不是“做题者”。这种“给定方案验证是否合法”的模型在现实中其实到处都有应用。最常见的例子是大学排课不同的考试科目就是顶点如果两门课有共同的学生就在它们之间连一条边颜色就代表考试时间段相邻科目不能同色。人工排好一个课表之后教务老师需要快速检查这份课表有没有冲突本质就是在做这道题的验证操作。另一个经典场景是无线频段分配多个通信基站之间存在干扰关系把每个基站看成顶点互相干扰的基站之间连边颜色代表不同频段目标是避免相邻基站使用相同频率。实际工程中也不可能每次重新做全局搜索更多是局部调整后验证合法性。图着色验证算法在这里承担的就是“检查员”角色。还有编译器后端里的寄存器分配问题这是图着色最著名的工业级应用之一程序中的变量是顶点同时活跃的变量之间连边颜色对应物理寄存器相邻顶点不能同色。编译器在生成代码前经常需要验证某个分配结果是否可行算法核心思想和PTA这道题一模一样只是规模更大、约束更多。如果你还想沿着这道题继续练手可以考虑几个变体如果N的值不是20而是几十万个查询怎么优化每次的验证速度这时你可能需要预先给每个颜色建立顶点集合然后检测同一颜色内部是否存在边用哈希集合把冲突检测从O(E)降到接近O(V)如果题目让你判断“是否存在至少一种合法方案”而不是“验证给定方案”那才是真正的NP难搜索问题得用回溯、分支限界甚至启发式算法。刷题的意义往往不在于记住某一道题的解法而在于把一道简单的题放进更大的坐标系里看清它在哪里它的前后左右都是什么。这道题处于“验证类图算法”这个位置理解这一点之后以后遇到任何方案验证型的问题你都会第一时间想到“先分组统计再逐项核对”这个套路。我个人在实际做题过程中比较深的体会是判断题的代码从来不是难点难点在于把所有隐藏条件找出来再逐条翻译成可以执行的if。拿到题先花五分钟把规则列成清单写代码五分钟再花十分钟构造边界用例这套流程看起来笨拙却能避开绝大多数提交返工的痛苦。