2026年6月GESP真题及题解（C++七级）：染色

题目描述

小杨同学有一张包含n nn个结点的无向图G GG,G GG中的结点依次以1 , 2 , … , n 1, 2, \dots, n1,2,…,n编号。

小杨同学发现G GG中每个结点的度数都是2 22。显然G GG中恰好有n nn条边。

小杨同学想为G GG中的结点染色，使得任意一条边两端的结点都有不同的颜色。

小杨同学想知道最少需要多少种颜色才能在满足条件的前提下为G GG染色。

输入格式

本题包含多组数据。

第一行，一个正整数t tt，表示数据组数。

对于每组数据：

第一行，一个正整数n nn，表示无向图G GG中的结点数。

接下来n nn行，每行两个正整数u i , v i u_i, v_iui​,vi​，表示一条连接结点u i u_iui​与v i v_ivi​的无向边，整数之间以空格分隔。

保证G GG中没有重边与自环。

输出格式

对于每组数据：输出一行，一个整数，表示在满足条件的前提下为G GG染色需要的最少颜色数。

输入输出样例 1

输入 1

4 6 1 6 2 1 3 2 4 3 5 4 6 5 6 1 3 3 5 5 1 2 4 4 6 6 2 3 1 2 2 3 3 1 5 1 4 2 5 3 1 4 2 5 3

输出 1

2 3 3 3

数据范围

对于40 % 40\%40%的测试点，保证∑ n ≤ 500 \sum n \le 500∑n≤500，∑ n \sum n∑n指每个输入中多组数据的n nn的总和。

对于所有测试点，保证1 ≤ t ≤ 100 1 \le t \le 1001≤t≤100，3 ≤ n ≤ 10 5 3 \le n \le 10^53≤n≤105，∑ n ≤ 10 5 \sum n \le 10^5∑n≤105。保证G GG中没有重边与自环。

思路分析

题目给出的是一个无向图，每个结点的度数均为 2，且没有重边和自环。
这样的图一定由若干个互不相连的简单环组成（每个连通分量都是一个环）。

对一条环上的结点染色，要求相邻结点颜色不同：

• 如果环的长度是偶数，可以用 2 种颜色交替染色。
• 如果环的长度是奇数，则至少需要 3 种颜色（因为 2 色会冲突）。

整个图的染色数取决于所有环中所需颜色数的最大值。
由于所有环都是独立的，且颜色可以重复使用，因此：

• 如果所有环的长度都是偶数，整个图是二分图，答案为2。
• 如果存在至少一个奇环，则答案为3。

判断一个图是否存在奇环，等价于判断图是否是二分图。
用黑白染色（BFS/DFS）遍历所有结点，若出现相邻结点颜色相同，则说明存在奇环。

算法步骤：

1. 读入数据组数t。
2. 对每组数据：
   • 读入n和n条边，建立邻接表。
   • 初始化颜色数组为 0（未染色）。
   • 对每个未染色的结点开始 BFS 染色，颜色用 1 和 2 表示。
   • 若发现冲突，标记存在奇环。
   • 输出结果：无冲突输出2，有冲突输出3。

时间复杂度 O(∑n)，空间复杂度 O(n)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintM=100005;vector<int>g[M];//邻接表，g[i]存储与结点i相连的所有结点intc[M];//染色标记：0未染色，1和2表示两种不同颜色intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cin>>t;while(t--){intn;cin>>n;//当前组结点数for(inti=1;i<=n;i++)g[i].clear();//清空上一组残留的邻接表for(inti=0;i<n;i++){//读入n条边（每个结点度数为2，总边数=n）intu,v;cin>>u>>v;g[u].push_back(v);//无向边，双向添加g[v].push_back(u);}for(inti=1;i<=n;i++)c[i]=0;//重置所有结点颜色为未染色boolok=true;//标记整个图是否为二分图，初始为truequeue<int>q;//BFS队列for(inti=1;i<=n&&ok;i++){//遍历所有结点，若已发现非二分则提前终止外层循环if(c[i]==0){//该结点尚未染色，以它为起点开始BFS染色一个新的连通分量c[i]=1;//起点染颜色1q.push(i);//入队while(!q.empty()&&ok){//队列非空且仍为二分图时继续intx=q.front();q.pop();//取出队首结点for(inty:g[x]){//遍历所有邻居if(c[y]==0){//未染色，染成与x相反的颜色（3-c[x]保证1↔2互换）c[y]=3-c[x];q.push(y);//新染色结点入队}elseif(c[y]==c[x]){//已染色且与当前结点同色，违反二分图条件（存在奇环）ok=false;//标记为非二分图break;//跳出内层for循环}}}}}cout<<(ok?2:3)<<"\n";//若为二分图需2种颜色，否则存在奇环需3种颜色}return0;}

功能分析

• 输入处理：支持多组数据，每组先读入结点数n，然后读入n条无向边。
• 建图：使用邻接表存储，每个结点度数均为 2。
• 二分图判定：通过 BFS 对每个连通分量进行黑白染色，遇到同色相邻边则判定为非二分图（存在奇环）。
• 输出结果：若整个图是二分图，输出2；否则输出3。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}