GESP2026年6月认证C++七级( 第三部分编程题（1、染色））精讲

这道GESP 七级 2026 年 6 月编程题第一题《染色》我认为是近年来七级中很有意思的一道图论题。它看起来像图染色很多同学一看到最少颜色四个字就会想到回溯搜索图着色DFS二分图判定四色定理实际上这些都不是本题真正的考点。真正的考点只有两个① 理解题目给出的特殊图结构② 奇环判定二分图判定很多同学如果没有读懂题目可能会写出指数级DFS搜索结果直接超时。下面我一步一步带大家理解这道题。第一幕来到染色王国1、有一天小杨来到了一座神奇的王国。这里有很多房子结点。房子之间用道路连接边。国王说为了方便邮递员送信任何两间相邻的房子都不能刷成同一种颜色。2、例如A —— B如果A刷红色B就不能刷红色。只能刷蓝色。3、这就是最经典的图染色问题。第二幕题目真正隐藏的信息1、有的同学一开始会忽略这一句话每个结点的度数都是2。2、这一句话非常重要1什么叫度数都是22例如○连两条边。○ / ○ \ ○每个点都只有两条边。不会多不会少。3、那这样的图长什么样我们画几个。1例如1 / \ 6 2 | | 5 3 \ / 4是不是一个圈2再看1——2——3 | | 6——5——4还是一个圈。3再画一个。1 / \ 3 —— 2也是一个圈。4、于是我们会发现所有点度数都是2。意味着整个图一定由若干个环组成。这是整道题最重要的突破口。很多同学做到这里已经成功一半了。5、为什么一定是环我们来思考。假设不是环。1例如1——2——3那么1只有一条边。度数就是1。违反题意。2如果1 | 2 | 3 | 4两端度数还是1。也不满足。3所以唯一可能就是一直绕回来。形成闭环。所以这是一张由多个独立环组成的图。第三幕什么时候两种颜色够1、先看偶数个点。例如1——2 | | 4——3四个点。我们试试染色。红 蓝 蓝 红成功。2、再画一个六边形。红 蓝 红 蓝 红 蓝最后还能接回来。没有问题。因此偶环只需要2种颜色。第四幕什么时候失败1、再看三角形。A / \ B —— C开始染色。1A 红。红2B只能蓝。红 蓝3C怎么办它同时连着A 和 B。如果红和A冲突。如果蓝和B冲突。没有颜色可选。所以三角形必须三种颜色。2、再画五边形。1 / \ 5 2 | | 4 —— 31染一下红 蓝 红 蓝 2最后一个点既不能红也不能蓝。仍然失败。因此所有奇数环都需要3种颜色。第五幕真正规律出来了1、于是整个题目突然变得特别简单。2、如果所有环都是偶数长度。答案23、如果出现任何一个奇环。答案34、是不是一下子简单了这就是本题真正的数学规律。第六幕那怎么判断奇环1、假设我们沿着环走。1→2→3→4→5→6→1走了一圈。数一下。6偶数。答案2。2、如果1→2→3→1长度3奇数。答案3。3、所以本题其实就是寻找所有环统计环长度奇偶性。第七幕参考程序#include iostream #include algorithm using namespace std; // n顶点个数 int n; // a[i]记录顶点 i 的第一个邻居 // b[i]记录顶点 i 的第二个邻居 // 因为题目保证每个点度数都是2所以只需要两个变量即可 int a[100010], b[100010]; // cnt[i]记录顶点 i 在当前环中的走了多少步 // 同时也可以表示该点是否已经访问过 int cnt[100010]; void solve() { cin n; // 初始化 for (int i 1; i n; i) { a[i] 0; b[i] 0; cnt[i] 0; } // 输入 n 条边 for (int i 1; i n; i) { int u, v; cin u v; // 每个点只有两个邻居 // 新读入的邻居放到 a[] // 原来的 a[] 挪到 b[] b[u] a[u]; a[u] v; b[v] a[v]; a[v] u; } // flagtrue 说明存在奇数环 bool flag false; // 枚举每一个点 for (int i 1; i n; i) { // 已经属于某个环跳过 if (cnt[i]) continue; // 从当前点开始沿着环走 int u i; // last表示上一个点 // 一开始假设是从第一个邻居走过来的 int last a[u]; // 计算下一步要走到哪里 // 一个点只有两个邻居 // // a[u] // \ // u // / // b[u] // // 已知来自 last // 那么下一步就是另外一个邻居 // // 利用 // // ab-last // // 就能得到另一个邻居 int v a[u] b[u] - last; // 沿着整个环一直走 while (!cnt[v]) { // 记录这是环中的第几步 cnt[v] cnt[u] 1; // 更新前驱 last u; // 向前走一步 u v; // 求下一个点 v a[u] b[u] - last; } // cnt[i] // 就是整个环长度-1 // 如果是奇数 // 说明这是奇数环 if (cnt[i] % 2 ! 0) flag true; } // 有奇环 if (flag) cout 3 endl; else cout 2 endl; } int main() { int t; cin t; while (t--) solve(); return 0; }第八幕为什么参考程序没有DFS1、有的同学看到参考程序会疑惑。它没有DFS。没有BFS。为什么2、来看代码a[u]v; b[u]...1它给每个点记录了两个邻居。因为每个点度数就是2。所以根本不用邻接表。一个点只有两个邻居。直接保存邻居1 邻居2就够了。2于是从某一点开始。例如1知道两个邻居。随便走一个。1→2到了2以后。2有两个邻居1 3因为刚刚来自1。所以下一步一定去3。3继续3又有两个邻居。去另一个。……4最终一定绕回来。这就是参考程序中的last变量的作用。5它表示我刚刚从哪里来的。这样就不会走回头路。第九幕cnt数组在干什么1、参考程序中cnt[v]cnt[u]1;其实它就是在记录走了多少步。2、例如1 ↓ 2 ↓ 3 ↓ 41cnt就是0 1 2 32最后回到起点。发现cnt33说明走了3条边。奇数。就是奇环。4所以程序最后判断if(cnt[i]%2!0)5就是这个环是不是奇环。第十幕为什么发现一个奇环就结束1、因为只要有一个奇环。整个图至少需要3种颜色。不会再变成2种。2、因此flagtrue;最后if(flag) 输出3 否则 输出2结束。本题考察的知识很多同学认为这是图染色。其实不是。真正考察的是✅ 图的特殊性质✅ 环✅ 奇偶性✅ 二分图判定其中一个图能够用两种颜色染色当且仅当它是二分图。而二分图没有奇环。这就是本题背后的理论。一句话总结整道题由于每个结点度数都是2所以整张图一定由若干个环组成偶数环可以用2种颜色染色奇数环必须用3种颜色因此只需要判断是否存在奇环即可。本题最容易掉进的三个陷阱1、陷阱一把它当成普通图染色很多同学会写DFS枚举所有颜色复杂度指数级。直接超时。2、陷阱二没有发现度数都是2这是整题最关键的突破口。一旦发现度数2整题难度立刻下降一大截。3、陷阱三不会把奇环和二分图联系起来七级图论最重要的一句话就是二分图 ⇔ 没有奇数环。本题实际上就是一道二分图判定的变形题只是利用了每个结点度数为2这一特殊性质把问题进一步简化成了检查每个环的长度奇偶性。理解了这一点以后再遇到类似的图染色题就能很快找到突破口。