1. 项目概述从一道算法题看图的着色与DFS遍历最近在准备算法竞赛或者刷题的朋友肯定对PTA程序设计类实验辅助教学平台上的L2级别题目不陌生。L2-023“图着色问题”就是其中一道非常经典的、考察图论基础与深度优先搜索DFS应用的题目。乍一看标题“图着色”、“DFS”、“C”、“邻接矩阵”这几个关键词组合在一起就勾勒出了一个清晰的解题轮廓我们需要用C语言基于邻接矩阵这种数据结构来存储图并利用DFS算法去判断一个给定的着色方案是否合法。这不仅仅是一道简单的“是”或“否”的判断题。它背后涉及的是图论中一个著名的NP难问题——图的着色问题Graph Coloring的简化版本。在实际场景中这个问题可以映射到很多领域比如编译器的寄存器分配相邻的变量不能分配到同一个寄存器、制定课程表同一时间不能安排有冲突的课程、无线通信的频率分配相邻基站不能使用相同频率等等。因此掌握这道题的解法不仅仅是学会一个算法模板更是理解一种将复杂现实约束抽象为图模型并加以解决的思维方式。今天我就以一个过来人的身份带大家从头到尾拆解这道L2-023。我会重点分享如何用邻接矩阵存图、如何设计DFS遍历逻辑来验证着色方案以及在这个过程中那些容易踩坑的细节。无论你是正在刷题的学生还是对图算法感兴趣的开发者相信这篇结合了原理、代码与实战心得的分享都能让你有所收获。2. 核心思路与方案选型为什么是邻接矩阵和DFS拿到题目第一步不是急着写代码而是彻底理解题意并选择合适的数据结构与算法。题目要求我们判断给定的颜色分配方案是否满足1) 相邻顶点颜色不同2) 恰好使用了K种颜色。这是一个典型的图遍历验证问题。2.1 数据结构选型邻接矩阵 vs. 邻接表存图逃不开邻接矩阵和邻接表这两种经典结构。邻接矩阵用一个二维数组G[V][V]表示G[i][j] 1表示顶点i和j之间有边。对于无向图矩阵是对称的。优点实现极其简单直观检查任意两个顶点是否相邻即是否有边是O(1)的时间复杂度这对于本题需要频繁判断“相邻点颜色是否相同”的操作非常友好。缺点空间复杂度是O(V²)对于顶点数V很大比如上万但边数E很少的稀疏图会造成巨大的空间浪费。不过PTA的题目通常数据规模可控L2级别的图V通常在10³量级以内使用邻接矩阵完全可行且代码简洁。邻接表用一个数组vectorint Adj[V]表示Adj[i]这个向量里存储了所有与顶点i相邻的顶点编号。优点空间复杂度是O(VE)适合稀疏图节省内存。缺点判断两个特定顶点是否相邻需要遍历其中一个顶点的邻接链表最坏情况是O(V)。代码实现相对矩阵稍复杂。选择理由对于本题核心操作是“给定一个着色方案遍历每个顶点检查其所有邻居的颜色是否与之相同”。使用邻接矩阵我们可以通过一个简单的双重循环外层遍历所有顶点i内层遍历所有顶点j来模拟这一检查内层判断G[i][j]1 color[i]color[j]即可逻辑清晰直白。虽然理论上邻接表遍历邻居的效率更高O(degree(i))但邻接矩阵的O(V)检查在数据规模不大时完全可接受且代码更容易写对在竞赛或限时场景下“简单可靠”往往比“极致优化”更重要。因此我选择使用邻接矩阵作为本题的存储结构。2.2 算法选型DFS vs. BFS vs. 直接枚举验证着色方案本质是验证图的每条边连接的两个顶点颜色是否不同。这不需要我们“搜索”一种着色方案而是“检查”一个给定的方案。直接枚举所有边最朴素的方法。读取着色方案后遍历所有边即邻接矩阵中所有为1的G[i][j]且ij以避免重复检查color[i]和color[j]是否相等。这种方法逻辑最简单也完全正确。DFS/BFS遍历从某个顶点开始遍历整个连通分量或整个图在遍历过程中检查当前顶点与其下一个将要访问的邻居顶点对于DFS是递归深入对于BFS是放入队列前的颜色是否冲突。这种方法更贴近“图遍历”的经典教学场景能很好地练习DFS/BFS的应用。选择理由题目要求用DFS那我们就用DFS。但我们要理解在这里DFS并非必须而是一种实现方式。用DFS的好处是它为解决更复杂的着色问题比如寻找一种可行的着色方案打下了基础。我们的DFS函数可以设计得非常简单其任务不是着色而是以当前顶点u为起点检查它的所有邻居v。如果发现color[u] color[v]则立即返回失败否则如果邻居v还未被访问过则递归地对v进行同样的检查。注意这里不需要“状态回溯”因为颜色是固定的我们只是在做验证。2.3 颜色种类校验的陷阱题目明确要求“颜色数必须等于K”而不是小于等于K。这是一个非常关键的边界条件也是本题主要的坑点之一。我们需要在检查完所有边的颜色冲突后额外统计实际用到的颜色种类数。统计方法最直接的是用一个setint来存储所有color[i]最后看set.size()是否等于K。但注意颜色编号题目并未指定范围使用set是通用且安全的。也有人用大小为N的bool数组但前提是知道颜色编号范围且不大。用set是更稳妥的选择。3. 代码实现与核心细节拆解理清了思路我们开始动手实现。我会分模块讲解代码并穿插解释每个细节背后的考量。3.1 数据结构定义与输入处理#include iostream #include vector #include set #include cstring // 用于memset using namespace std; const int MAXV 510; // 根据题目数据范围设定适当留有余量 int G[MAXV][MAXV]; // 邻接矩阵 int color[MAXV]; // 存储每个顶点的颜色 bool visited[MAXV]; // DFS访问标记数组 int V, E, K; // 顶点数、边数、颜色数常量定义MAXV设为510是因为题目通常V在500左右多开一点防止边界溢出。这是刷题时的好习惯。全局变量将图、颜色、访问数组以及基本参数设为全局变量可以避免在DFS函数中传递大量参数简化代码。在算法竞赛中这是常见做法。int main() { // 读取图的基本信息 cin V E K; memset(G, 0, sizeof(G)); // 初始化邻接矩阵为0无边 for (int i 0; i E; i) { int a, b; cin a b; // 题目顶点编号通常从1开始我们存储时也按此习惯方便映射 G[a][b] G[b][a] 1; // 无向图 } // ... 后续处理查询 }注意顶点编号的起始索引0还是1必须与题目输入保持一致。PTA题目通常从1开始所以我们的数组也从下标1开始使用下标0空置。这一点务必仔细读题。3.2 DFS验证函数的设计这是核心函数它负责验证以顶点u所在的连通分量内是否存在相邻点同色的情况。bool dfsCheck(int u) { visited[u] true; // 标记当前顶点已访问 // 遍历所有顶点找到u的邻居 for (int v 1; v V; v) { if (G[u][v] 1) { // v是u的邻居 if (color[u] color[v]) { return false; // 发现冲突立即返回false } if (!visited[v]) { // 如果邻居v还没被检查过 if (!dfsCheck(v)) { // 递归检查v所在的子图 return false; // 如果子图检查失败 propagate失败 } } } } return true; // 所有邻居检查完毕均无冲突 }关键点解析递归终止条件递归的“深度”由图的连通性决定。当某个顶点的所有邻居都被访问过或者发现颜色冲突时递归就会返回。冲突检测位置在判断v是u的邻居后立即检查颜色是否相同。这个检查必须在递归进入v之前进行。因为我们要保证每一条边的两个端点颜色不同。访问数组的作用visited数组防止对同一个顶点进行重复检查避免无限递归。注意这里visited的含义是“该顶点是否已在本轮方案验证中被DFS过程处理过”每一轮新的方案验证都需要重新初始化这个数组。返回值传递一旦在某个递归层发现冲突通过return false将失败状态层层传递回最开始的调用处效率很高。3.3 主逻辑与颜色种类校验主函数中我们需要处理多个查询。int queryNum; cin queryNum; while (queryNum--) { setint colorSet; // 1. 读取一种着色方案 for (int i 1; i V; i) { cin color[i]; colorSet.insert(color[i]); // 顺便收集颜色种类 } // 2. 检查颜色种类数是否为K if (colorSet.size() ! K) { cout No endl; continue; // 直接判断下一个方案 } // 3. 初始化访问数组准备DFS验证 memset(visited, false, sizeof(visited)); bool isValid true; // 4. 图可能不连通需要对每个未访问的顶点启动DFS for (int i 1; i V; i) { if (!visited[i]) { if (!dfsCheck(i)) { isValid false; break; // 一个连通分量失败整个方案即失败 } } } // 5. 输出结果 cout (isValid ? Yes : No) endl; }核心步骤解读边读边存在读取每个顶点颜色时直接插入set利用其自动去重的特性。先验条件判断在启动耗时的DFS遍历之前先判断颜色数。如果不等于K直接输出“No”可以节省大量时间。这是一个重要的优化。处理非连通图for循环从1到V对每个未访问的顶点调用dfsCheck。这确保了即使图有多个连通分量每个分量都会被检查到。dfsCheck(i)会标记并检查顶点i所在整个连通分量。提前退出在遍历连通分量的循环中一旦某个分量检查失败 (isValidfalse)立即break不再检查剩余分量提升效率。4. 常见“坑点”与调试心得即便思路清晰实现这道题时还是有几个地方容易出错。下面是我在多次提交中总结出来的“血泪教训”。4.1 坑点一对“K种颜色”的理解偏差这是最大的坑。题目描述是“需要使每种颜色都被使用”即颜色种类数必须等于K而不是小于等于K。错误做法只检查了相邻点颜色不同没有检查颜色数。错误做法用数组统计颜色但默认颜色编号是连续整数且从1开始。如果方案是{1, 3, 5}K3用数组统计colorCount[1], colorCount[3], colorCount[5]然后遍历1到K发现colorCount[2]0就判错。但颜色编号可能不是从1开始也可能不连续。所以必须用set来统计实际出现的不同颜色编号。测试用例V3边(1,2), (2,3)K2。方案{1, 2, 1}是合法的用了1和2两种颜色。方案{1, 1, 2}是非法的相邻点1和2同色。方案{1, 2, 2}是非法的相邻点2和3同色。方案{1, 2, 3}也是非法的用了1,2,3三种颜色不等于K2。4.2 坑点二DFS函数中的重复检查与访问标记在dfsCheck中我们遍历所有顶点v来判断是否为邻居。对于无向图边(u, v)和(v, u)是等价的。潜在问题当检查顶点u时我们会检查邻居v。当递归进入v后又会检查其邻居u此时color[u] color[v]已经在上一轮检查过虽然因为visited[u]true不会再次递归但依然会执行一次if (color[v] color[u])的判断。这不会导致逻辑错误但有一点点冗余。这不是Bug这种冗余检查是无害的代码逻辑是正确的。更精细的写法可以只遍历v u的邻居但会稍微增加代码复杂度。在竞赛中清晰正确比微优化更重要。4.3 坑点三每轮查询初始化的重要性visited数组必须在每一轮新的着色方案验证前重新初始化为false。如果忘了重置上一轮方案的访问状态会影响到下一轮导致DFS可能跳过某些顶点造成误判。牢记在while (queryNum--)循环内部读取完color数组后紧接着就要memset(visited, false, sizeof(visited));。4.4 坑点四顶点编号起始索引这是一个低级但常见的错误。题目输入“顶点数V边数E”然后输入E行每行两个整数代表一条边。务必确认这些整数是从0开始还是从1开始。PTA的图论题目绝大多数情况下顶点编号是从1开始的连续整数。我们的数组G、color、visited也应该从下标1开始使用将下标0的空间空出或忽略。如果按从0开始处理会导致数组越界或逻辑错误。4.5 调试技巧与测试用例设计自己设计几个小而精的测试用例比盲目提交更有效。基础用例连通图输入 3 2 2 // V3, E2, K2 1 2 2 3 1 // 1个查询 1 2 1 // 方案 输出应为Yes颜色数不足K... (图同上) 1 1 1 1 // 只用了1种颜色K2 输出应为No颜色数超过K... (图同上) 1 1 2 3 // 用了3种颜色K2 输出应为No非连通图输入 5 3 3 // 两个连通分量(1-2-3) 和 (4-5) 1 2 2 3 4 5 1 1 2 3 4 5 // 5种颜色不检查实际种类{1,2,3,4,5} size5 ! K3 输出应为No另一个非连通图合法案例... (图同上) 1 1 2 1 3 3 // 颜色集合 {1,2,3} size3 K3且各分量内无冲突 输出应为Yes自环与重边通常PTA的测试数据不会包含自环边连接同一顶点但理论上我们的邻接矩阵处理自环G[i][i]1会导致DFS中自己检查自己颜色肯定冲突。重边G[i][j]被多次赋值为1不影响逻辑。我们的代码能正确处理这些情况。在本地运行这些用例确保输出完全正确再提交到在线判题系统能大大提高一次通过的几率。5. 算法扩展与性能思考虽然我们用了DFS但正如之前分析的直接枚举边是更直观的解法。这里给出一个“枚举边”版本的伪代码作为对比bool checkByEdge() { setint colorSet(color 1, color V 1); // 用数组区间构造set if (colorSet.size() ! K) return false; for (int i 1; i V; i) { for (int j i 1; j V; j) { // j从i1开始避免重复检查边(i,j)和(j,i) if (G[i][j] 1 color[i] color[j]) { return false; } } } return true; }两种方法的对比时间复杂度都是 O(V²)因为邻接矩阵遍历是O(V²)枚举边最坏也是O(V²)。对于稀疏图枚举边法内层循环j可以优化为只遍历邻居但需要邻接表支持。空间复杂度都是 O(V²)邻接矩阵。可读性枚举边法更直白更容易理解“检查每条边”这个题意。DFS法更体现“遍历”思想。适用性DFS法是解决“寻找一种着色方案”或“判断图是否可K着色”等更一般性问题的基石。本题只是其一个特例验证给定方案。关于性能在V500的量级下O(V²)250,000次操作对于多组查询比如100组总操作数在10^7量级在C中是完全可以在1秒内完成的。如果V更大达到几千就需要考虑使用邻接表存储并将验证算法优化到O(VE)的复杂度。最后这道L2-023“图着色问题”是一个很好的综合练习它串联了图的基本存储邻接矩阵、遍历算法DFS、条件判断颜色种类以及细致的边界处理。理解并熟练实现它对你掌握图论算法的基本思维和代码实现能力都大有裨益。在平时练习时不妨两种方法DFS验证和枚举边验证都实现一遍并思考如果题目变成“判断该图是否可K着色”这是一个经典的回溯算法问题又该如何修改代码。多进行这样的举一反三算法能力才能真正得到提升。 图着色问题详解：邻接矩阵与DFS算法在PTA L2-023中的应用
1. 项目概述从一道算法题看图的着色与DFS遍历最近在准备算法竞赛或者刷题的朋友肯定对PTA程序设计类实验辅助教学平台上的L2级别题目不陌生。L2-023“图着色问题”就是其中一道非常经典的、考察图论基础与深度优先搜索DFS应用的题目。乍一看标题“图着色”、“DFS”、“C”、“邻接矩阵”这几个关键词组合在一起就勾勒出了一个清晰的解题轮廓我们需要用C语言基于邻接矩阵这种数据结构来存储图并利用DFS算法去判断一个给定的着色方案是否合法。这不仅仅是一道简单的“是”或“否”的判断题。它背后涉及的是图论中一个著名的NP难问题——图的着色问题Graph Coloring的简化版本。在实际场景中这个问题可以映射到很多领域比如编译器的寄存器分配相邻的变量不能分配到同一个寄存器、制定课程表同一时间不能安排有冲突的课程、无线通信的频率分配相邻基站不能使用相同频率等等。因此掌握这道题的解法不仅仅是学会一个算法模板更是理解一种将复杂现实约束抽象为图模型并加以解决的思维方式。今天我就以一个过来人的身份带大家从头到尾拆解这道L2-023。我会重点分享如何用邻接矩阵存图、如何设计DFS遍历逻辑来验证着色方案以及在这个过程中那些容易踩坑的细节。无论你是正在刷题的学生还是对图算法感兴趣的开发者相信这篇结合了原理、代码与实战心得的分享都能让你有所收获。2. 核心思路与方案选型为什么是邻接矩阵和DFS拿到题目第一步不是急着写代码而是彻底理解题意并选择合适的数据结构与算法。题目要求我们判断给定的颜色分配方案是否满足1) 相邻顶点颜色不同2) 恰好使用了K种颜色。这是一个典型的图遍历验证问题。2.1 数据结构选型邻接矩阵 vs. 邻接表存图逃不开邻接矩阵和邻接表这两种经典结构。邻接矩阵用一个二维数组G[V][V]表示G[i][j] 1表示顶点i和j之间有边。对于无向图矩阵是对称的。优点实现极其简单直观检查任意两个顶点是否相邻即是否有边是O(1)的时间复杂度这对于本题需要频繁判断“相邻点颜色是否相同”的操作非常友好。缺点空间复杂度是O(V²)对于顶点数V很大比如上万但边数E很少的稀疏图会造成巨大的空间浪费。不过PTA的题目通常数据规模可控L2级别的图V通常在10³量级以内使用邻接矩阵完全可行且代码简洁。邻接表用一个数组vectorint Adj[V]表示Adj[i]这个向量里存储了所有与顶点i相邻的顶点编号。优点空间复杂度是O(VE)适合稀疏图节省内存。缺点判断两个特定顶点是否相邻需要遍历其中一个顶点的邻接链表最坏情况是O(V)。代码实现相对矩阵稍复杂。选择理由对于本题核心操作是“给定一个着色方案遍历每个顶点检查其所有邻居的颜色是否与之相同”。使用邻接矩阵我们可以通过一个简单的双重循环外层遍历所有顶点i内层遍历所有顶点j来模拟这一检查内层判断G[i][j]1 color[i]color[j]即可逻辑清晰直白。虽然理论上邻接表遍历邻居的效率更高O(degree(i))但邻接矩阵的O(V)检查在数据规模不大时完全可接受且代码更容易写对在竞赛或限时场景下“简单可靠”往往比“极致优化”更重要。因此我选择使用邻接矩阵作为本题的存储结构。2.2 算法选型DFS vs. BFS vs. 直接枚举验证着色方案本质是验证图的每条边连接的两个顶点颜色是否不同。这不需要我们“搜索”一种着色方案而是“检查”一个给定的方案。直接枚举所有边最朴素的方法。读取着色方案后遍历所有边即邻接矩阵中所有为1的G[i][j]且ij以避免重复检查color[i]和color[j]是否相等。这种方法逻辑最简单也完全正确。DFS/BFS遍历从某个顶点开始遍历整个连通分量或整个图在遍历过程中检查当前顶点与其下一个将要访问的邻居顶点对于DFS是递归深入对于BFS是放入队列前的颜色是否冲突。这种方法更贴近“图遍历”的经典教学场景能很好地练习DFS/BFS的应用。选择理由题目要求用DFS那我们就用DFS。但我们要理解在这里DFS并非必须而是一种实现方式。用DFS的好处是它为解决更复杂的着色问题比如寻找一种可行的着色方案打下了基础。我们的DFS函数可以设计得非常简单其任务不是着色而是以当前顶点u为起点检查它的所有邻居v。如果发现color[u] color[v]则立即返回失败否则如果邻居v还未被访问过则递归地对v进行同样的检查。注意这里不需要“状态回溯”因为颜色是固定的我们只是在做验证。2.3 颜色种类校验的陷阱题目明确要求“颜色数必须等于K”而不是小于等于K。这是一个非常关键的边界条件也是本题主要的坑点之一。我们需要在检查完所有边的颜色冲突后额外统计实际用到的颜色种类数。统计方法最直接的是用一个setint来存储所有color[i]最后看set.size()是否等于K。但注意颜色编号题目并未指定范围使用set是通用且安全的。也有人用大小为N的bool数组但前提是知道颜色编号范围且不大。用set是更稳妥的选择。3. 代码实现与核心细节拆解理清了思路我们开始动手实现。我会分模块讲解代码并穿插解释每个细节背后的考量。3.1 数据结构定义与输入处理#include iostream #include vector #include set #include cstring // 用于memset using namespace std; const int MAXV 510; // 根据题目数据范围设定适当留有余量 int G[MAXV][MAXV]; // 邻接矩阵 int color[MAXV]; // 存储每个顶点的颜色 bool visited[MAXV]; // DFS访问标记数组 int V, E, K; // 顶点数、边数、颜色数常量定义MAXV设为510是因为题目通常V在500左右多开一点防止边界溢出。这是刷题时的好习惯。全局变量将图、颜色、访问数组以及基本参数设为全局变量可以避免在DFS函数中传递大量参数简化代码。在算法竞赛中这是常见做法。int main() { // 读取图的基本信息 cin V E K; memset(G, 0, sizeof(G)); // 初始化邻接矩阵为0无边 for (int i 0; i E; i) { int a, b; cin a b; // 题目顶点编号通常从1开始我们存储时也按此习惯方便映射 G[a][b] G[b][a] 1; // 无向图 } // ... 后续处理查询 }注意顶点编号的起始索引0还是1必须与题目输入保持一致。PTA题目通常从1开始所以我们的数组也从下标1开始使用下标0空置。这一点务必仔细读题。3.2 DFS验证函数的设计这是核心函数它负责验证以顶点u所在的连通分量内是否存在相邻点同色的情况。bool dfsCheck(int u) { visited[u] true; // 标记当前顶点已访问 // 遍历所有顶点找到u的邻居 for (int v 1; v V; v) { if (G[u][v] 1) { // v是u的邻居 if (color[u] color[v]) { return false; // 发现冲突立即返回false } if (!visited[v]) { // 如果邻居v还没被检查过 if (!dfsCheck(v)) { // 递归检查v所在的子图 return false; // 如果子图检查失败 propagate失败 } } } } return true; // 所有邻居检查完毕均无冲突 }关键点解析递归终止条件递归的“深度”由图的连通性决定。当某个顶点的所有邻居都被访问过或者发现颜色冲突时递归就会返回。冲突检测位置在判断v是u的邻居后立即检查颜色是否相同。这个检查必须在递归进入v之前进行。因为我们要保证每一条边的两个端点颜色不同。访问数组的作用visited数组防止对同一个顶点进行重复检查避免无限递归。注意这里visited的含义是“该顶点是否已在本轮方案验证中被DFS过程处理过”每一轮新的方案验证都需要重新初始化这个数组。返回值传递一旦在某个递归层发现冲突通过return false将失败状态层层传递回最开始的调用处效率很高。3.3 主逻辑与颜色种类校验主函数中我们需要处理多个查询。int queryNum; cin queryNum; while (queryNum--) { setint colorSet; // 1. 读取一种着色方案 for (int i 1; i V; i) { cin color[i]; colorSet.insert(color[i]); // 顺便收集颜色种类 } // 2. 检查颜色种类数是否为K if (colorSet.size() ! K) { cout No endl; continue; // 直接判断下一个方案 } // 3. 初始化访问数组准备DFS验证 memset(visited, false, sizeof(visited)); bool isValid true; // 4. 图可能不连通需要对每个未访问的顶点启动DFS for (int i 1; i V; i) { if (!visited[i]) { if (!dfsCheck(i)) { isValid false; break; // 一个连通分量失败整个方案即失败 } } } // 5. 输出结果 cout (isValid ? Yes : No) endl; }核心步骤解读边读边存在读取每个顶点颜色时直接插入set利用其自动去重的特性。先验条件判断在启动耗时的DFS遍历之前先判断颜色数。如果不等于K直接输出“No”可以节省大量时间。这是一个重要的优化。处理非连通图for循环从1到V对每个未访问的顶点调用dfsCheck。这确保了即使图有多个连通分量每个分量都会被检查到。dfsCheck(i)会标记并检查顶点i所在整个连通分量。提前退出在遍历连通分量的循环中一旦某个分量检查失败 (isValidfalse)立即break不再检查剩余分量提升效率。4. 常见“坑点”与调试心得即便思路清晰实现这道题时还是有几个地方容易出错。下面是我在多次提交中总结出来的“血泪教训”。4.1 坑点一对“K种颜色”的理解偏差这是最大的坑。题目描述是“需要使每种颜色都被使用”即颜色种类数必须等于K而不是小于等于K。错误做法只检查了相邻点颜色不同没有检查颜色数。错误做法用数组统计颜色但默认颜色编号是连续整数且从1开始。如果方案是{1, 3, 5}K3用数组统计colorCount[1], colorCount[3], colorCount[5]然后遍历1到K发现colorCount[2]0就判错。但颜色编号可能不是从1开始也可能不连续。所以必须用set来统计实际出现的不同颜色编号。测试用例V3边(1,2), (2,3)K2。方案{1, 2, 1}是合法的用了1和2两种颜色。方案{1, 1, 2}是非法的相邻点1和2同色。方案{1, 2, 2}是非法的相邻点2和3同色。方案{1, 2, 3}也是非法的用了1,2,3三种颜色不等于K2。4.2 坑点二DFS函数中的重复检查与访问标记在dfsCheck中我们遍历所有顶点v来判断是否为邻居。对于无向图边(u, v)和(v, u)是等价的。潜在问题当检查顶点u时我们会检查邻居v。当递归进入v后又会检查其邻居u此时color[u] color[v]已经在上一轮检查过虽然因为visited[u]true不会再次递归但依然会执行一次if (color[v] color[u])的判断。这不会导致逻辑错误但有一点点冗余。这不是Bug这种冗余检查是无害的代码逻辑是正确的。更精细的写法可以只遍历v u的邻居但会稍微增加代码复杂度。在竞赛中清晰正确比微优化更重要。4.3 坑点三每轮查询初始化的重要性visited数组必须在每一轮新的着色方案验证前重新初始化为false。如果忘了重置上一轮方案的访问状态会影响到下一轮导致DFS可能跳过某些顶点造成误判。牢记在while (queryNum--)循环内部读取完color数组后紧接着就要memset(visited, false, sizeof(visited));。4.4 坑点四顶点编号起始索引这是一个低级但常见的错误。题目输入“顶点数V边数E”然后输入E行每行两个整数代表一条边。务必确认这些整数是从0开始还是从1开始。PTA的图论题目绝大多数情况下顶点编号是从1开始的连续整数。我们的数组G、color、visited也应该从下标1开始使用将下标0的空间空出或忽略。如果按从0开始处理会导致数组越界或逻辑错误。4.5 调试技巧与测试用例设计自己设计几个小而精的测试用例比盲目提交更有效。基础用例连通图输入 3 2 2 // V3, E2, K2 1 2 2 3 1 // 1个查询 1 2 1 // 方案 输出应为Yes颜色数不足K... (图同上) 1 1 1 1 // 只用了1种颜色K2 输出应为No颜色数超过K... (图同上) 1 1 2 3 // 用了3种颜色K2 输出应为No非连通图输入 5 3 3 // 两个连通分量(1-2-3) 和 (4-5) 1 2 2 3 4 5 1 1 2 3 4 5 // 5种颜色不检查实际种类{1,2,3,4,5} size5 ! K3 输出应为No另一个非连通图合法案例... (图同上) 1 1 2 1 3 3 // 颜色集合 {1,2,3} size3 K3且各分量内无冲突 输出应为Yes自环与重边通常PTA的测试数据不会包含自环边连接同一顶点但理论上我们的邻接矩阵处理自环G[i][i]1会导致DFS中自己检查自己颜色肯定冲突。重边G[i][j]被多次赋值为1不影响逻辑。我们的代码能正确处理这些情况。在本地运行这些用例确保输出完全正确再提交到在线判题系统能大大提高一次通过的几率。5. 算法扩展与性能思考虽然我们用了DFS但正如之前分析的直接枚举边是更直观的解法。这里给出一个“枚举边”版本的伪代码作为对比bool checkByEdge() { setint colorSet(color 1, color V 1); // 用数组区间构造set if (colorSet.size() ! K) return false; for (int i 1; i V; i) { for (int j i 1; j V; j) { // j从i1开始避免重复检查边(i,j)和(j,i) if (G[i][j] 1 color[i] color[j]) { return false; } } } return true; }两种方法的对比时间复杂度都是 O(V²)因为邻接矩阵遍历是O(V²)枚举边最坏也是O(V²)。对于稀疏图枚举边法内层循环j可以优化为只遍历邻居但需要邻接表支持。空间复杂度都是 O(V²)邻接矩阵。可读性枚举边法更直白更容易理解“检查每条边”这个题意。DFS法更体现“遍历”思想。适用性DFS法是解决“寻找一种着色方案”或“判断图是否可K着色”等更一般性问题的基石。本题只是其一个特例验证给定方案。关于性能在V500的量级下O(V²)250,000次操作对于多组查询比如100组总操作数在10^7量级在C中是完全可以在1秒内完成的。如果V更大达到几千就需要考虑使用邻接表存储并将验证算法优化到O(VE)的复杂度。最后这道L2-023“图着色问题”是一个很好的综合练习它串联了图的基本存储邻接矩阵、遍历算法DFS、条件判断颜色种类以及细致的边界处理。理解并熟练实现它对你掌握图论算法的基本思维和代码实现能力都大有裨益。在平时练习时不妨两种方法DFS验证和枚举边验证都实现一遍并思考如果题目变成“判断该图是否可K着色”这是一个经典的回溯算法问题又该如何修改代码。多进行这样的举一反三算法能力才能真正得到提升。