1. 项目概述从一道题看算法竞赛中的图论基础最近在带学生刷PTA程序设计类实验辅助教学平台的题目L2-023“图着色问题”这道题被问到的频率相当高。很多同学第一次接触时会觉得题目描述有点绕“给定一个图再给一种颜色分配方案判断它是不是一个合法的图着色方案”。这听起来像是个纯粹的判断题但背后考察的知识点非常扎实是检验你是否真正理解图遍历和图着色定义的试金石。这道题本身不要求你去找出着色方案那是经典的图着色算法比如回溯法或Welch-Powell算法要解决的问题而是给你一个现成的方案让你验证这实际上降低了不少难度但陷阱也埋在这里——如果你对“合法着色”的定义理解有偏差或者遍历图的姿势不对就很容易掉坑里。简单来说这道题的核心就是给你一个无向图顶点和边的关系再给你一个颜色序列每个顶点涂了什么颜色你需要判断这个涂色方案是否满足“图着色问题”的两个硬性要求第一任何一条边连接的两个顶点不能颜色相同这保证了是“正常着色”第二使用的颜色种类数必须恰好等于题目指定的K种。这就像给你一幅已经涂好颜色的地图让你检查是否相邻的省份都用了不同颜色并且颜色盘里只用到了规定的那几种颜料。在C的语境下解决它考验的是你如何高效地存储图、如何无遗漏地遍历所有边以及如何巧妙地利用STL容器来统计和判断颜色。我见过不少初学者用二维数组邻接矩阵存了图然后写两层循环去检查这在小规模数据下没问题但一旦顶点数上千边数上万这种O(V²)的检查在OJ上很可能就超时了。更优雅的做法是使用邻接表然后遍历每条边进行判断。下面我就结合自己多次ACAccepted通过和帮学生Debug的经验把这道题的解题思路、代码实现细节以及那些容易踩的坑掰开揉碎了讲清楚。2. 核心思路拆解与数据结构选型2.1 问题本质与输入输出分析首先我们得彻底读懂题目的输入输出格式这是正确解题的第一步。题目输入大致分为三块图的基本信息顶点数V正整数不超过500、边数E、以及待检查的着色方案数N。图的边关系接下来的E行每行给出两个顶点编号从1开始连续编号表示一条无向边。这里隐含了图是简单图的约定即没有自环连接自己和重边相同顶点对的多条边。待检查的方案每个方案占一行给出V个整数第i个整数表示顶点i的颜色编号。颜色用正整数表示。输出很简单对每个方案如果它是满足要求的“图着色方案”输出“Yes”否则输出“No”。这里的关键在于理解“满足要求”的两条准则准则一相邻异色对于图中的每一条边 (a, b)必须满足color[a] ! color[b]。这是图着色最核心的约束。准则二颜色数限定方案中实际使用的不同颜色数量必须等于题目给定的K不能多也不能少。这是一个非常容易忽略的陷阱很多同学只检查了第一条看到样例过了就提交结果只能拿到部分分数。2.2 数据结构的选择为什么是邻接表存储图我们主要有邻接矩阵和邻接表两种方式。对于这道题顶点数V≤500边数E未知但理论上最多可达V*(V-1)/2大约12万条。如果用邻接矩阵二维数组G[501][501]检查时需要两层循环遍历整个矩阵复杂度是O(V²)对于500的规模是25万次检查尚可接受。但PTA的题目常常会卡时间和空间效率养成使用更优数据结构的习惯至关重要。邻接表是更优的选择。它只存储实际存在的边空间复杂度是O(VE)。在检查时我们只需要遍历所有存储的边复杂度是O(E)对于稀疏图E远小于V²效率提升明显。在C中实现邻接表最方便的就是使用vector数组。vectorint adj[501]; // 邻接表adj[i]存储所有与顶点i相邻的顶点输入边时int a, b; cin a b; adj[a].push_back(b); adj[b].push_back(a); // 无向图需要添加两次注意这里有一个小技巧。由于顶点编号从1开始我们直接声明adj[501]舍弃下标0这样顶点的编号和数组下标就能直接对应避免在访问时频繁地进行-1操作减少出错也提升代码可读性。2.3 算法流程设计整个判断算法可以清晰地分为三步读取着色方案将V个颜色读入一个数组color[501]中。检查准则一相邻异色遍历邻接表adj。对于每个顶点i遍历它的所有邻居j。如果发现color[i] color[j]则立刻判定该方案非法输出“No”并跳出检查。检查准则二颜色数限定如果通过了准则一的检查那么我们需要统计方案中使用了多少种不同的颜色。这里最适合的工具就是unordered_set哈希集合。将color[1]到color[V]全部插入到一个unordered_setint colorSet中然后检查colorSet.size() K是否成立。成立则输出“Yes”否则输出“No”。这个流程清晰且高效两步检查的顺序也很重要。先做O(E)的边检查如果失败则提前退出避免不必要的颜色统计操作。3. 代码实现与逐行解析理解了思路我们来看完整的C代码实现。我会在关键代码后加上详细注释。#include iostream #include vector #include unordered_set using namespace std; int main() { int V, E, K, N; cin V E K; // 读取顶点数、边数、颜色数K // 1. 构建邻接表 vectorint adj[501]; // 下标从1开始使用 for (int i 0; i E; i) { int a, b; cin a b; adj[a].push_back(b); adj[b].push_back(a); // 无向边双向添加 } cin N; // 读取方案数 while (N--) { // 2. 读取当前着色方案 int color[501] {0}; // 初始化颜色数组0表示未赋值实际不会用到0号顶点 unordered_setint colorSet; // 用于统计颜色种类 bool isValid true; // 标志位初始认为方案有效 for (int i 1; i V; i) { cin color[i]; colorSet.insert(color[i]); // 顺便插入集合为后续统计做准备 } // 3. 检查准则一任何一条边的两端颜色不能相同 for (int i 1; i V isValid; i) { for (int neighbor : adj[i]) { // 注意由于是无向图每条边会被遍历两次i-neighbor 和 neighbor-i // 为了避免重复判断和防止ineighbor时的重复检查我们可以添加一个条件 // 但最简单直接且不会出错的方法是当发现非法时立即终止。 if (color[i] color[neighbor]) { isValid false; break; // 发现一条非法边立即跳出内层循环 } } // 如果内层循环因为发现非法而break此处isValid已是false外层循环条件 isValid会使其终止 } // 4. 检查准则二颜色种类数必须等于K if (isValid) { if (colorSet.size() ! K) { isValid false; } } // 5. 输出结果 cout (isValid ? Yes : No) endl; } return 0; }关键点解析与避坑指南邻接表遍历与重复判断问题代码中注释提到了对于无向边(a,b)它既存储在adj[a]中也存储在adj[b]中。当我们用两层循环遍历所有顶点及其所有邻居时边(a,b)会被检查两次一次当ia检查到b一次当ib检查到a。这并不影响结果的正确性因为只要有一次检查失败整个方案就是非法的。有些人会通过判断i neighbor来只检查一次这样可以提升一点效率但代码会稍复杂。在竞赛中清晰正确优先这点微小的效率损失通常可以接受。颜色统计的时机我在读取颜色数组的同时就将其插入了unordered_set。这是一个小优化将O(V)的统计时间合并到了读取的O(V)时间里总时间复杂度和分开做是一样的但代码更简洁。注意unordered_set的插入操作平均时间复杂度是O(1)比遍历完再用set插入要高效。isValid标志位的使用使用一个布尔标志位来控制流程是很好的习惯。一旦在边检查中发现非法立即设置isValidfalse并跳出循环避免后续无意义的检查。在输出时用三元运算符简洁地输出结果。关于K0的特殊情况题目中K是正整数所以不存在K0的情况。但如果是一些变体题需要考虑如果K0那么只有所有顶点都没有颜色或颜色数为0才合法这是一个边界条件。4. 常见错误与深度排查在实际提交和教学过程中我总结了同学们最容易出现的几种错误以及背后的原因。4.1 错误类型一只判邻边忽略颜色数K这是最常见的失分点。题目要求“使用的颜色数恰好为K”而不是“不超过K”。很多同学用set统计后直接判断colorSet.size() K这是错误的。必须用。错误示例if (colorSet.size() K) { // 错误必须是 K cout Yes endl; }背后的原因对问题定义理解不严谨。图着色问题Graph Coloring通常讨论的是“最少需要多少种颜色”色数或者“在给定颜色数量下是否存在一种着色方案”。本题是后者的判定版本且要求“恰好使用K种颜色”这是一个更强的约束。务必仔细读题。4.2 错误类型二图存储或遍历不当数组越界顶点编号从1开始如果数组大小只开了V访问color[V]或adj[V]就会越界。必须开V1的大小通常直接开一个稍大的固定值如505更安全。忽略无向边输入边(a,b)时只向adj[a]添加了b忘记了向adj[b]添加a导致图结构错误检查会漏掉一半的边。遍历逻辑错误在检查边时错误地遍历了所有顶点对(i, j)i从1到V,j从1到V而不是遍历邻接表。这会将不存在的边也纳入检查如果这些不存在的边两端颜色恰巧相同就会误判。一定要遍历的是实际存在的边。4.3 错误类型三输入处理与循环控制方案数N的循环错误使用while(N--)是标准做法。但要注意在循环内部每个方案开始前color数组和colorSet都需要重新初始化。不能把上一个方案的数据带到下一个方案。颜色编号类型题目说颜色是正整数但没给范围。用int存储足够。但要注意颜色编号可能很大不过对于unordered_set来说没有影响。4.4 性能优化与测试用例设计虽然本题数据规模不大但养成考虑性能的习惯很重要。输入输出加速在PTA这类OJ平台当输入输出数据量很大时可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);来关闭C流与C标准流的同步可以显著提升读写速度。这在处理大量方案N很大时效果明显。测试自己可以设计几个极端用例来测试程序最大图V500E约为12万完全图K500。检查程序是否超时或内存超限。最小颜色数K1。合法的方案只有所有顶点颜色相同且图必须是无边图因为任何一条边的两端颜色都会相同。如果你的程序对K1且图中有边的方案输出“Yes”那就错了。颜色数不符设计一个方案相邻顶点颜色都不同但用了K1或K-1种颜色确保程序能正确输出“No”。5. 从本题延伸的图论学习建议L2-023作为一个验证性问题其实打开了图论算法的一扇大门。解决它之后你可以尝试思考更深入的问题如果让你来着色怎么办这就是经典的图着色算法。你可以尝试实现回溯算法给一个小图比如V20寻找用K种颜色着色的方案。进一步可以学习Welch-Powell算法这是一种贪心算法虽然不能保证得到最少的颜色数即色数但能在多项式时间内给出一个不错的着色方案。判断更复杂的着色问题比如“列表着色”List Coloring每个顶点有一个可用的颜色列表只能从列表中选择颜色。或者“边着色”Edge Coloring问题。关联实际应用图着色不仅仅是理论问题。它对应着非常多的实际调度问题考试安排每个顶点是一门课程边代表有共同学生的课程冲突颜色代表考试时间段。用最少的颜色时间段完成所有考试。寄存器分配在编译器优化中变量是顶点如果两个变量同时存活则需要边颜色是CPU寄存器。目标是用有限的寄存器颜色容纳尽可能多的变量。无线网络信道分配基站是顶点如果距离过近会产生干扰则连边颜色是不同的通信信道。把一道题做透不仅仅是AC更要理解其背后的模型、掌握通用的解题方法如邻接表存图、遍历边检查约束、利用STL进行统计并思考其延伸和应用这样刷题的效果才是最好的。对于C学习者这道题也是一个绝佳的练习让你熟悉vector、unordered_set这些容器的实战用法。下次再遇到类似的“验证型”图论问题比如判断是否为二分图、是否存在环等你就能触类旁通了。
1. 项目概述从一道题看算法竞赛中的图论基础最近在带学生刷PTA程序设计类实验辅助教学平台的题目L2-023“图着色问题”这道题被问到的频率相当高。很多同学第一次接触时会觉得题目描述有点绕“给定一个图再给一种颜色分配方案判断它是不是一个合法的图着色方案”。这听起来像是个纯粹的判断题但背后考察的知识点非常扎实是检验你是否真正理解图遍历和图着色定义的试金石。这道题本身不要求你去找出着色方案那是经典的图着色算法比如回溯法或Welch-Powell算法要解决的问题而是给你一个现成的方案让你验证这实际上降低了不少难度但陷阱也埋在这里——如果你对“合法着色”的定义理解有偏差或者遍历图的姿势不对就很容易掉坑里。简单来说这道题的核心就是给你一个无向图顶点和边的关系再给你一个颜色序列每个顶点涂了什么颜色你需要判断这个涂色方案是否满足“图着色问题”的两个硬性要求第一任何一条边连接的两个顶点不能颜色相同这保证了是“正常着色”第二使用的颜色种类数必须恰好等于题目指定的K种。这就像给你一幅已经涂好颜色的地图让你检查是否相邻的省份都用了不同颜色并且颜色盘里只用到了规定的那几种颜料。在C的语境下解决它考验的是你如何高效地存储图、如何无遗漏地遍历所有边以及如何巧妙地利用STL容器来统计和判断颜色。我见过不少初学者用二维数组邻接矩阵存了图然后写两层循环去检查这在小规模数据下没问题但一旦顶点数上千边数上万这种O(V²)的检查在OJ上很可能就超时了。更优雅的做法是使用邻接表然后遍历每条边进行判断。下面我就结合自己多次ACAccepted通过和帮学生Debug的经验把这道题的解题思路、代码实现细节以及那些容易踩的坑掰开揉碎了讲清楚。2. 核心思路拆解与数据结构选型2.1 问题本质与输入输出分析首先我们得彻底读懂题目的输入输出格式这是正确解题的第一步。题目输入大致分为三块图的基本信息顶点数V正整数不超过500、边数E、以及待检查的着色方案数N。图的边关系接下来的E行每行给出两个顶点编号从1开始连续编号表示一条无向边。这里隐含了图是简单图的约定即没有自环连接自己和重边相同顶点对的多条边。待检查的方案每个方案占一行给出V个整数第i个整数表示顶点i的颜色编号。颜色用正整数表示。输出很简单对每个方案如果它是满足要求的“图着色方案”输出“Yes”否则输出“No”。这里的关键在于理解“满足要求”的两条准则准则一相邻异色对于图中的每一条边 (a, b)必须满足color[a] ! color[b]。这是图着色最核心的约束。准则二颜色数限定方案中实际使用的不同颜色数量必须等于题目给定的K不能多也不能少。这是一个非常容易忽略的陷阱很多同学只检查了第一条看到样例过了就提交结果只能拿到部分分数。2.2 数据结构的选择为什么是邻接表存储图我们主要有邻接矩阵和邻接表两种方式。对于这道题顶点数V≤500边数E未知但理论上最多可达V*(V-1)/2大约12万条。如果用邻接矩阵二维数组G[501][501]检查时需要两层循环遍历整个矩阵复杂度是O(V²)对于500的规模是25万次检查尚可接受。但PTA的题目常常会卡时间和空间效率养成使用更优数据结构的习惯至关重要。邻接表是更优的选择。它只存储实际存在的边空间复杂度是O(VE)。在检查时我们只需要遍历所有存储的边复杂度是O(E)对于稀疏图E远小于V²效率提升明显。在C中实现邻接表最方便的就是使用vector数组。vectorint adj[501]; // 邻接表adj[i]存储所有与顶点i相邻的顶点输入边时int a, b; cin a b; adj[a].push_back(b); adj[b].push_back(a); // 无向图需要添加两次注意这里有一个小技巧。由于顶点编号从1开始我们直接声明adj[501]舍弃下标0这样顶点的编号和数组下标就能直接对应避免在访问时频繁地进行-1操作减少出错也提升代码可读性。2.3 算法流程设计整个判断算法可以清晰地分为三步读取着色方案将V个颜色读入一个数组color[501]中。检查准则一相邻异色遍历邻接表adj。对于每个顶点i遍历它的所有邻居j。如果发现color[i] color[j]则立刻判定该方案非法输出“No”并跳出检查。检查准则二颜色数限定如果通过了准则一的检查那么我们需要统计方案中使用了多少种不同的颜色。这里最适合的工具就是unordered_set哈希集合。将color[1]到color[V]全部插入到一个unordered_setint colorSet中然后检查colorSet.size() K是否成立。成立则输出“Yes”否则输出“No”。这个流程清晰且高效两步检查的顺序也很重要。先做O(E)的边检查如果失败则提前退出避免不必要的颜色统计操作。3. 代码实现与逐行解析理解了思路我们来看完整的C代码实现。我会在关键代码后加上详细注释。#include iostream #include vector #include unordered_set using namespace std; int main() { int V, E, K, N; cin V E K; // 读取顶点数、边数、颜色数K // 1. 构建邻接表 vectorint adj[501]; // 下标从1开始使用 for (int i 0; i E; i) { int a, b; cin a b; adj[a].push_back(b); adj[b].push_back(a); // 无向边双向添加 } cin N; // 读取方案数 while (N--) { // 2. 读取当前着色方案 int color[501] {0}; // 初始化颜色数组0表示未赋值实际不会用到0号顶点 unordered_setint colorSet; // 用于统计颜色种类 bool isValid true; // 标志位初始认为方案有效 for (int i 1; i V; i) { cin color[i]; colorSet.insert(color[i]); // 顺便插入集合为后续统计做准备 } // 3. 检查准则一任何一条边的两端颜色不能相同 for (int i 1; i V isValid; i) { for (int neighbor : adj[i]) { // 注意由于是无向图每条边会被遍历两次i-neighbor 和 neighbor-i // 为了避免重复判断和防止ineighbor时的重复检查我们可以添加一个条件 // 但最简单直接且不会出错的方法是当发现非法时立即终止。 if (color[i] color[neighbor]) { isValid false; break; // 发现一条非法边立即跳出内层循环 } } // 如果内层循环因为发现非法而break此处isValid已是false外层循环条件 isValid会使其终止 } // 4. 检查准则二颜色种类数必须等于K if (isValid) { if (colorSet.size() ! K) { isValid false; } } // 5. 输出结果 cout (isValid ? Yes : No) endl; } return 0; }关键点解析与避坑指南邻接表遍历与重复判断问题代码中注释提到了对于无向边(a,b)它既存储在adj[a]中也存储在adj[b]中。当我们用两层循环遍历所有顶点及其所有邻居时边(a,b)会被检查两次一次当ia检查到b一次当ib检查到a。这并不影响结果的正确性因为只要有一次检查失败整个方案就是非法的。有些人会通过判断i neighbor来只检查一次这样可以提升一点效率但代码会稍复杂。在竞赛中清晰正确优先这点微小的效率损失通常可以接受。颜色统计的时机我在读取颜色数组的同时就将其插入了unordered_set。这是一个小优化将O(V)的统计时间合并到了读取的O(V)时间里总时间复杂度和分开做是一样的但代码更简洁。注意unordered_set的插入操作平均时间复杂度是O(1)比遍历完再用set插入要高效。isValid标志位的使用使用一个布尔标志位来控制流程是很好的习惯。一旦在边检查中发现非法立即设置isValidfalse并跳出循环避免后续无意义的检查。在输出时用三元运算符简洁地输出结果。关于K0的特殊情况题目中K是正整数所以不存在K0的情况。但如果是一些变体题需要考虑如果K0那么只有所有顶点都没有颜色或颜色数为0才合法这是一个边界条件。4. 常见错误与深度排查在实际提交和教学过程中我总结了同学们最容易出现的几种错误以及背后的原因。4.1 错误类型一只判邻边忽略颜色数K这是最常见的失分点。题目要求“使用的颜色数恰好为K”而不是“不超过K”。很多同学用set统计后直接判断colorSet.size() K这是错误的。必须用。错误示例if (colorSet.size() K) { // 错误必须是 K cout Yes endl; }背后的原因对问题定义理解不严谨。图着色问题Graph Coloring通常讨论的是“最少需要多少种颜色”色数或者“在给定颜色数量下是否存在一种着色方案”。本题是后者的判定版本且要求“恰好使用K种颜色”这是一个更强的约束。务必仔细读题。4.2 错误类型二图存储或遍历不当数组越界顶点编号从1开始如果数组大小只开了V访问color[V]或adj[V]就会越界。必须开V1的大小通常直接开一个稍大的固定值如505更安全。忽略无向边输入边(a,b)时只向adj[a]添加了b忘记了向adj[b]添加a导致图结构错误检查会漏掉一半的边。遍历逻辑错误在检查边时错误地遍历了所有顶点对(i, j)i从1到V,j从1到V而不是遍历邻接表。这会将不存在的边也纳入检查如果这些不存在的边两端颜色恰巧相同就会误判。一定要遍历的是实际存在的边。4.3 错误类型三输入处理与循环控制方案数N的循环错误使用while(N--)是标准做法。但要注意在循环内部每个方案开始前color数组和colorSet都需要重新初始化。不能把上一个方案的数据带到下一个方案。颜色编号类型题目说颜色是正整数但没给范围。用int存储足够。但要注意颜色编号可能很大不过对于unordered_set来说没有影响。4.4 性能优化与测试用例设计虽然本题数据规模不大但养成考虑性能的习惯很重要。输入输出加速在PTA这类OJ平台当输入输出数据量很大时可以在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);来关闭C流与C标准流的同步可以显著提升读写速度。这在处理大量方案N很大时效果明显。测试自己可以设计几个极端用例来测试程序最大图V500E约为12万完全图K500。检查程序是否超时或内存超限。最小颜色数K1。合法的方案只有所有顶点颜色相同且图必须是无边图因为任何一条边的两端颜色都会相同。如果你的程序对K1且图中有边的方案输出“Yes”那就错了。颜色数不符设计一个方案相邻顶点颜色都不同但用了K1或K-1种颜色确保程序能正确输出“No”。5. 从本题延伸的图论学习建议L2-023作为一个验证性问题其实打开了图论算法的一扇大门。解决它之后你可以尝试思考更深入的问题如果让你来着色怎么办这就是经典的图着色算法。你可以尝试实现回溯算法给一个小图比如V20寻找用K种颜色着色的方案。进一步可以学习Welch-Powell算法这是一种贪心算法虽然不能保证得到最少的颜色数即色数但能在多项式时间内给出一个不错的着色方案。判断更复杂的着色问题比如“列表着色”List Coloring每个顶点有一个可用的颜色列表只能从列表中选择颜色。或者“边着色”Edge Coloring问题。关联实际应用图着色不仅仅是理论问题。它对应着非常多的实际调度问题考试安排每个顶点是一门课程边代表有共同学生的课程冲突颜色代表考试时间段。用最少的颜色时间段完成所有考试。寄存器分配在编译器优化中变量是顶点如果两个变量同时存活则需要边颜色是CPU寄存器。目标是用有限的寄存器颜色容纳尽可能多的变量。无线网络信道分配基站是顶点如果距离过近会产生干扰则连边颜色是不同的通信信道。把一道题做透不仅仅是AC更要理解其背后的模型、掌握通用的解题方法如邻接表存图、遍历边检查约束、利用STL进行统计并思考其延伸和应用这样刷题的效果才是最好的。对于C学习者这道题也是一个绝佳的练习让你熟悉vector、unordered_set这些容器的实战用法。下次再遇到类似的“验证型”图论问题比如判断是否为二分图、是否存在环等你就能触类旁通了。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
