【题目来源】

洛谷：P17014 [GESP202606 七级] 染色 - 洛谷

【题目描述】

小杨同学有一张包含 $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$ 染色需要的最少颜色数。

【输入样例】

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

【输出样例】

2
3
3
3

【核心思想】

1. 问题分析：给定一个每个结点度数均为 $2$ 的无向图 $G$，即 $G$ 由若干个不相交的环组成（每个连通块是一个简单环）。要求为结点染色使得相邻结点颜色不同，求最少颜色数。这是一个图论性质分析 + 连通块分类问题，核心在于利用"每个结点度数为 $2$"的条件推导出图的结构特征，进而确定每个连通块的色数。

2. 算法选择：

   • 图结构分析：度数为 $2$ 的无向图必然由若干个简单环构成（无重边、无自环保证）
   • 环的色数判定：偶环是二分图，色数为 $2$；奇环不是二分图，色数为 $3$
   • 深度优先搜索（DFS）：统计每个连通块的结点数，判断奇偶性

3. 关键步骤：

   • 建图：读入 $n$ 条边，建立无向图的邻接表
   • 连通块遍历（对每个未访问的结点 $i$）：
     • $cnt\leftarrow 0$，启动 $dfs(i)$ 统计连通块大小
     • 若 $cnt\mathrm{mod}2=0$：$res\leftarrow 2$（偶环，二分图，$2$ 色可染）
     • 若 $cnt\mathrm{mod}2=1$：$res\leftarrow 3$（奇环，非二分图，需 $3$ 色）
     • $ans\leftarrow \max (ans,res)$
   • 输出结果：$ans$

4. 时间/空间复杂度：

   • 时间复杂度：$O(t\cdot (n+m))=O(t\cdot n)$，其中 $m=n$（每个结点度数为 $2$），DFS 遍历每个连通块一次
   • 空间复杂度：$O(n)$，邻接表和访问标记数组

5. 图论性质分析的核心思想：

   • 度数约束推导结构：无向图中所有结点度数为 $2$ 且无重边、无自环，则图必然由若干个不相交的简单环组成。每个连通块是一个环，结点数等于边数
   • 二分图与色数：偶环是二分图，可以用 $2$ 种颜色交替染色；奇环包含奇数长度的回路，不是二分图，根据 Brooks 定理和具体结构分析，需要 $3$ 种颜色
   • 全局最优取最大：整个图的最少颜色数等于所有连通块色数的最大值（各连通块独立染色，颜色可复用）
   • DFS 统计连通块：利用访问标记数组和 DFS 遍历，高效统计每个连通块的结点数，无需显式找环
   • 适用于具有特殊度数约束的图结构分析、连通块分类判定类问题

【算法标签】

#普及 #DFS-图

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;              // 常量：最大结点数

int t;                             // t: 数据组数
int n;                             // n: 当前数据的结点数
vector<int> g[N];                  // g[x]: 结点 x 的邻接结点列表
bool vis[N];                       // vis[x]: 标记结点 x 是否已被访问
int cnt;                           // cnt: 当前连通块的结点数

void dfs(int x)                    // 深度优先搜索，统计连通块大小
{
    vis[x] = true;                 // 标记当前结点已访问
    cnt++;                         // 连通块结点数加一

    for (int i = 0; i < g[x].size(); i++)  // 遍历所有邻接结点
    {
        int y = g[x][i];           // y: 邻接结点

        if (vis[y])                // 如果已访问，跳过
            continue;

        dfs(y);                    // 递归搜索
    }
}

int main()
{
    cin >> t;                      // 读入数据组数

    while (t--)                    // 循环处理每组数据
    {
        cin >> n;                  // 读入结点数

        for (int i = 1; i <= n; i++)  // 清空邻接表
            g[i].clear();

        for (int i = 1; i <= n; i++)  // 读入 n 条边
        {
            int u, v;              // u, v: 边的两个端点
            cin >> u >> v;
            g[u].push_back(v);     // 建立无向图
            g[v].push_back(u);
        }

        memset(vis, 0, sizeof(vis));  // 清空访问标记

        int ans = -1;              // ans: 最少需要的颜色数
        int res;                   // res: 当前连通块需要的颜色数

        for (int i = 1; i <= n; i++)  // 枚举每个结点，处理所有连通块
        {
            cnt = 0;               // 重置连通块计数器

            if (!vis[i])            // 如果结点 i 未被访问（新的连通块）
                dfs(i);

            if (cnt % 2 == 1)       // 如果连通块结点数为奇数
                res = 3;           // 奇环需要 3 种颜色
            else                    // 如果连通块结点数为偶数
                res = 2;           // 偶环只需要 2 种颜色

            ans = max(ans, res);    // 取所有连通块颜色数的最大值
        }

        cout << ans << endl;       // 输出最少需要的颜色数
    }

    return 0;
}

【运行结果】

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