GESP 202606 七级 T1题解
2026-06-28 22:54:01
发布于：江苏
11阅读
0回复
0点赞
刚考完七级！
题意分析
给定一张有 个节点， 条边，每个节点的度数都为 的图，为节点上色，要求每条边连接的两个顶点颜色不同，问最少需要几种颜色。
解题思路
介绍一种比较新颖的做法。
题目中描述了一张图，但是没有说是联通的，所以需要考虑每一个子图，然后因为子图之间不受影响，所以仅需求出其中的最大值即可。
接下来考虑每一个连通子图。拥有 个节点的连通子图中，每一个节点的度数都为 ，可以知道一共有 条边，还能得出一个更关键的信息：这个子图可以一笔画（拥有 个或 个度数为奇数的连通图可以一笔画）。因此可以将一个连通图拉成一条链表示。例如题中的样例三，就可以拉成 1 4 2 5 3 的链。接下来问题就转化成了：为一条长度为 的链上色，要求开头与结尾颜色不同，且相邻的两个节点颜色不同，至少要用几种颜色。
接下来用数字代指颜色，考虑分类讨论：若 为奇数，可以使用 1 2 1 2 1 2 ... 的构造方式，可最后结尾是 ，开头也是 ，因此需要将结尾换成 ，一共使用 种颜色；若 为偶数，依然可以使用 1 2 1 2 1 2 ... 的构造方式，结尾是 ，开头是 ，符合规则，使用 种颜色。
总而言之，若一个连通子图有 个节点，若 为奇数，则需 种颜色，若 为偶数，则需 种颜色。
但是是否需要考虑 的情况呢？不，当 时，那个节点的度数将为 ，而题目保证每个节点的度数都为 所以不可能出现 的情况。
接下来只需用 bfs 或 dfs 统计每个联通子图的大小就行了。时间复杂度 。
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int cal (int x) {
if (x % 2 == 1) return 3; //如果是奇数，则需要 3 种颜色
return 2; //如果是偶数，则需要 2 种颜色
}
int T, n;
bool vis[N];
vector <int> g[N]; //邻接表存图
void init () { //初始化
n = 0;
for (int i = 0; i < N; i++) {
vis[i] = false;
g[i].clear();
}
}
int bfs (int st) { //统计 st 所在的连通子图的大小
int ans = 0;
queue <int> q;
q.push(st); //起始节点入队
vis[st] = true; //标记
while (!q.empty()) {
ans++; //新节点
int u = q.front();
q.pop();
for (auto v : g[u]) { //遍历 u 的相邻节点
if (!vis[v]) { //如果没有被访问过
vis[v] = true; //标记
q.push(v); //入队
}
}
}
return ans;
}
void solve () {
init(); //初始化
//输入
cin >> n;
for (int i = 1; i <= n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector <int> siz; //统计每个子图的大小
for (int i = 1; i <= n; i++) {
if (!vis[i]) { //如果还没有被遍历到，说明有新的连通子图，开始遍历
siz.push_back(bfs(i)); //加入新子图的大小
}
}
int maxn = -2e9; //统计子图所需颜色种数的最大值
for (auto p : siz) {
maxn = max(maxn, cal(p)); //若有多个连通子图，选择需求量最大的
}
cout << maxn << '\n';
}
int main() {
cin >> T;
while (T--) {
solve();
}
return 0;
}
作者考试时第二题没有做出来 T-T
（这份代码应该是对的，暂时还没有提交，错了我会 update 的，反正考试时做对了）
有帮助，赞一个