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输入 14 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输出 12 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≤1003 ≤ 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遍历所有结点若出现相邻结点颜色相同则说明存在奇环。算法步骤读入数据组数t。对每组数据读入n和n条边建立邻接表。初始化颜色数组为 0未染色。对每个未染色的结点开始 BFS 染色颜色用 1 和 2 表示。若发现冲突标记存在奇环。输出结果无冲突输出2有冲突输出3。时间复杂度 O(∑n)空间复杂度 O(n)。代码实现#includebits/stdc.husingnamespacestd;constintM100005;vectorintg[M];//邻接表g[i]存储与结点i相连的所有结点intc[M];//染色标记0未染色1和2表示两种不同颜色intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cint;while(t--){intn;cinn;//当前组结点数for(inti1;in;i)g[i].clear();//清空上一组残留的邻接表for(inti0;in;i){//读入n条边每个结点度数为2总边数nintu,v;cinuv;g[u].push_back(v);//无向边双向添加g[v].push_back(u);}for(inti1;in;i)c[i]0;//重置所有结点颜色为未染色booloktrue;//标记整个图是否为二分图初始为truequeueintq;//BFS队列for(inti1;inok;i){//遍历所有结点若已发现非二分则提前终止外层循环if(c[i]0){//该结点尚未染色以它为起点开始BFS染色一个新的连通分量c[i]1;//起点染颜色1q.push(i);//入队while(!q.empty()ok){//队列非空且仍为二分图时继续intxq.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]){//已染色且与当前结点同色违反二分图条件存在奇环okfalse;//标记为非二分图break;//跳出内层for循环}}}}}cout(ok?2:3)\n;//若为二分图需2种颜色否则存在奇环需3种颜色}return0;}功能分析输入处理支持多组数据每组先读入结点数n然后读入n条无向边。建图使用邻接表存储每个结点度数均为 2。二分图判定通过 BFS 对每个连通分量进行黑白染色遇到同色相邻边则判定为非二分图存在奇环。输出结果若整个图是二分图输出2否则输出3。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
