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

这道GESP 七级 2026 年 6 月编程题第一题《染色》，我认为是近年来七级中，很有意思的一道图论题。

它看起来像图染色，很多同学一看到"最少颜色"四个字，就会想到：

• 回溯搜索？

• 图着色DFS？

• 二分图判定？

• 四色定理？

实际上，这些都不是本题真正的考点。

真正的考点只有两个：

① 理解题目给出的特殊图结构

② 奇环判定（二分图判定）

很多同学如果没有读懂题目，可能会写出指数级DFS搜索，结果直接超时。

下面我一步一步带大家理解这道题。

第一幕：来到"染色王国"

1、有一天，小杨来到了一座神奇的王国。

这里有很多房子（结点）。

房子之间用道路连接（边）。

国王说：

"为了方便邮递员送信，任何两间相邻的房子，都不能刷成同一种颜色。"

2、例如：

A —— B

如果A刷红色，

B就不能刷红色。

只能刷蓝色。

3、这就是最经典的

图染色问题。

第二幕：题目真正隐藏的信息

1、有的同学一开始，会忽略这一句话：

每个结点的度数都是2。

2、这一句话非常重要！

（1）什么叫度数都是2？

（2）例如

○

连两条边。

○ / ○ \ ○

每个点

都只有两条边。

不会多，

不会少。

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

开始染色。

（1）A 红。

红

（2）B

只能蓝。

红 蓝

（3）C怎么办？

它同时连着

A 和 B。

如果红：

和A冲突。

如果蓝：

和B冲突。

没有颜色可选。

所以：

三角形必须三种颜色。

2、再画五边形。

1 / \ 5 2 | | 4 —— 3

（1）染一下：

红 蓝 红 蓝 ？

（2）最后一个点

既不能红，

也不能蓝。

仍然失败。

因此：

所有奇数环都需要3种颜色。

第五幕：真正规律出来了

1、于是：

整个题目突然变得特别简单。

2、如果所有环都是偶数长度。

答案：

2

3、如果出现任何一个奇环。

答案：

3

4、是不是一下子简单了？

这就是本题真正的数学规律。

第六幕：那怎么判断奇环？

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; } // flag=true 说明存在奇数环 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 // 那么下一步就是另外一个邻居 // // 利用： // // a+b-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; }

第八幕：为什么参考程序没有DFS？

1、有的同学看到参考程序会疑惑。

它没有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 ↓ 4

（1）cnt就是：

0 1 2 3

（2）最后：

回到起点。

发现：

cnt=3

（3）说明：

走了3条边。

奇数。

就是奇环。

（4）所以：

程序最后判断：

if(cnt[i]%2!=0)

（5）就是：

这个环是不是奇环。

第十幕：为什么发现一个奇环就结束？

1、因为：

只要有一个奇环。

整个图

至少需要3种颜色。

不会再变成2种。

2、因此：

flag=true;

最后：

if(flag) 输出3 否则 输出2

结束。

本题考察的知识

很多同学认为这是：

图染色。

其实不是。

真正考察的是：

✅ 图的特殊性质

✅ 环

✅ 奇偶性

✅ 二分图判定

其中：

一个图能够用两种颜色染色，当且仅当它是二分图。

而：

二分图没有奇环。

这就是本题背后的理论。

一句话总结整道题

由于每个结点度数都是2，所以整张图一定由若干个环组成；偶数环可以用2种颜色染色，奇数环必须用3种颜色，因此只需要判断是否存在奇环即可。

本题最容易掉进的三个陷阱

1、陷阱一：把它当成普通图染色

很多同学会写：

DFS枚举所有颜色

复杂度指数级。

直接超时。

2、陷阱二：没有发现"度数都是2"

这是整题最关键的突破口。

一旦发现：

度数=2

整题难度立刻下降一大截。

3、陷阱三：不会把奇环和二分图联系起来

七级图论最重要的一句话就是：

二分图 ⇔ 没有奇数环。

本题实际上就是一道二分图判定的变形题，只是利用了"每个结点度数为2"这一特殊性质，把问题进一步简化成了检查每个环的长度奇偶性。理解了这一点，以后再遇到类似的图染色题，就能很快找到突破口。