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

题目描述

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

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

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

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

输入格式

本题包含多组数据。

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

对于每组数据：

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

接下来 $n$ 行，每行两个正整数 $u_i,v_i$，表示一条连接结点 $u_i$ 与 $v_i$ 的无向边，整数之间以空格分隔。

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

输出格式

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

输入输出样例 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\%$ 的测试点，保证 $\sum n\le 500$，$\sum n$ 指每个输入中多组数据的 $n$ 的总和。

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

思路分析

题目给出的是一个无向图，每个结点的度数均为 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>
using namespace std;

const int M=100005;
vector<int> g[M];//邻接表，g[i]存储与结点i相连的所有结点
int c[M];//染色标记：0未染色，1和2表示两种不同颜色

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

---

功能分析

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

---

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

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

【秘籍汇总】（完整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>
using namespace std;
int main(){
	cout<<"跟着王老师一起学习信奥赛C++";
	cout<<"    成就更好的自己！       ";
	cout<<"  csp信奥赛一等奖属于你!   ";
	return 0;
}