1. 项目概述：从一道题看算法竞赛中的图论基础

最近在带学生刷PTA（程序设计类实验辅助教学平台）的题目，L2-023“图着色问题”这道题被问到的频率相当高。很多同学第一次接触时，会觉得题目描述有点绕：“给定一个图，再给一种颜色分配方案，判断它是不是一个合法的图着色方案”。这听起来像是个纯粹的判断题，但背后考察的知识点非常扎实，是检验你是否真正理解图遍历和图着色定义的试金石。这道题本身不要求你去找出着色方案（那是经典的图着色算法，比如回溯法或Welch-Powell算法要解决的问题），而是给你一个现成的方案让你验证，这实际上降低了不少难度，但陷阱也埋在这里——如果你对“合法着色”的定义理解有偏差，或者遍历图的姿势不对，就很容易掉坑里。

简单来说，这道题的核心就是：给你一个无向图（顶点和边的关系），再给你一个颜色序列（每个顶点涂了什么颜色），你需要判断这个涂色方案是否满足“图着色问题”的两个硬性要求：第一，任何一条边连接的两个顶点不能颜色相同（这保证了是“正常着色”）；第二，使用的颜色种类数必须恰好等于题目指定的K种。这就像给你一幅已经涂好颜色的地图，让你检查是否相邻的省份都用了不同颜色，并且颜色盘里只用到了规定的那几种颜料。在C++的语境下解决它，考验的是你如何高效地存储图、如何无遗漏地遍历所有边，以及如何巧妙地利用STL容器来统计和判断颜色。

我见过不少初学者用二维数组邻接矩阵存了图，然后写两层循环去检查，这在小规模数据下没问题，但一旦顶点数上千，边数上万，这种O(V²)的检查在OJ上很可能就超时了。更优雅的做法是使用邻接表，然后遍历每条边进行判断。下面，我就结合自己多次AC（Accepted，通过）和帮学生Debug的经验，把这道题的解题思路、代码实现细节以及那些容易踩的坑，掰开揉碎了讲清楚。

2. 核心思路拆解与数据结构选型

2.1 问题本质与输入输出分析

首先，我们得彻底读懂题目的输入输出格式，这是正确解题的第一步。题目输入大致分为三块：

1. 图的基本信息：顶点数V（正整数，不超过500）、边数E、以及待检查的着色方案数N。
2. 图的边关系：接下来的E行，每行给出两个顶点编号（从1开始连续编号），表示一条无向边。这里隐含了图是简单图的约定，即没有自环（连接自己）和重边（相同顶点对的多条边）。
3. 待检查的方案：每个方案占一行，给出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(V+E)。在检查时，我们只需要遍历所有存储的边，复杂度是O(E)，对于稀疏图（E远小于V²）效率提升明显。在C++中，实现邻接表最方便的就是使用vector数组。

vector<int> 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 算法流程设计

整个判断算法可以清晰地分为三步：

1. 读取着色方案：将V个颜色读入一个数组color[501]中。
2. 检查准则一（相邻异色）：遍历邻接表adj。对于每个顶点i，遍历它的所有邻居j。如果发现color[i] == color[j]，则立刻判定该方案非法，输出“No”并跳出检查。
3. 检查准则二（颜色数限定）：如果通过了准则一的检查，那么我们需要统计方案中使用了多少种不同的颜色。这里最适合的工具就是unordered_set（哈希集合）。将color[1]到color[V]全部插入到一个unordered_set<int> 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. 构建邻接表 vector<int> 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_set<int> 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） // 为了避免重复判断和防止i<neighbor时的重复检查，我们可以添加一个条件 // 但最简单直接且不会出错的方法是：当发现非法时立即终止。 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; }

关键点解析与避坑指南：

1. 邻接表遍历与重复判断问题：代码中注释提到了，对于无向边(a,b)，它既存储在adj[a]中，也存储在adj[b]中。当我们用两层循环遍历所有顶点及其所有邻居时，边(a,b)会被检查两次（一次当i=a检查到b，一次当i=b检查到a）。这并不影响结果的正确性，因为只要有一次检查失败，整个方案就是非法的。有些人会通过判断i < neighbor来只检查一次，这样可以提升一点效率，但代码会稍复杂。在竞赛中，清晰正确优先，这点微小的效率损失通常可以接受。

2. 颜色统计的时机：我在读取颜色数组的同时，就将其插入了unordered_set。这是一个小优化，将O(V)的统计时间合并到了读取的O(V)时间里，总时间复杂度和分开做是一样的，但代码更简洁。注意，unordered_set的插入操作平均时间复杂度是O(1)，比遍历完再用set插入要高效。

3. isValid标志位的使用：使用一个布尔标志位来控制流程是很好的习惯。一旦在边检查中发现非法，立即设置isValid=false并跳出循环，避免后续无意义的检查。在输出时，用三元运算符简洁地输出结果。

4. 关于K=0的特殊情况：题目中K是正整数，所以不存在K=0的情况。但如果是一些变体题，需要考虑如果K=0，那么只有所有顶点都没有颜色（或颜色数为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]就会越界。必须开V+1的大小，通常直接开一个稍大的固定值（如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很大）时效果明显。
• 测试自己：可以设计几个极端用例来测试程序：
  1. 最大图：V=500，E约为12万（完全图），K=500。检查程序是否超时或内存超限。
  2. 最小颜色数：K=1。合法的方案只有所有顶点颜色相同，且图必须是无边图（因为任何一条边的两端颜色都会相同）。如果你的程序对K=1且图中有边的方案输出“Yes”，那就错了。
  3. 颜色数不符：设计一个方案，相邻顶点颜色都不同，但用了K+1或K-1种颜色，确保程序能正确输出“No”。

5. 从本题延伸的图论学习建议

L2-023作为一个验证性问题，其实打开了图论算法的一扇大门。解决它之后，你可以尝试思考更深入的问题：

1. 如果让你来着色怎么办？这就是经典的图着色算法。你可以尝试实现回溯算法，给一个小图（比如V<=20）寻找用K种颜色着色的方案。进一步，可以学习Welch-Powell算法，这是一种贪心算法，虽然不能保证得到最少的颜色数（即色数），但能在多项式时间内给出一个不错的着色方案。
2. 判断更复杂的着色问题：比如“列表着色”（List Coloring），每个顶点有一个可用的颜色列表，只能从列表中选择颜色。或者“边着色”（Edge Coloring）问题。
3. 关联实际应用：图着色不仅仅是理论问题。它对应着非常多的实际调度问题：
   • 考试安排：每个顶点是一门课程，边代表有共同学生的课程冲突，颜色代表考试时间段。用最少的颜色（时间段）完成所有考试。
   • 寄存器分配：在编译器优化中，变量是顶点，如果两个变量同时存活则需要边，颜色是CPU寄存器。目标是用有限的寄存器（颜色）容纳尽可能多的变量。
   • 无线网络信道分配：基站是顶点，如果距离过近会产生干扰则连边，颜色是不同的通信信道。

把一道题做透，不仅仅是AC，更要理解其背后的模型、掌握通用的解题方法（如邻接表存图、遍历边检查约束、利用STL进行统计），并思考其延伸和应用，这样刷题的效果才是最好的。对于C++学习者，这道题也是一个绝佳的练习，让你熟悉vector、unordered_set这些容器的实战用法。下次再遇到类似的“验证型”图论问题，比如判断是否为二分图、是否存在环等，你就能触类旁通了。