题解：洛谷 P17014 [GESP202606 七级] 染色

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P17014 [GESP202606 七级] 染色 - 洛谷【题目描述】小杨同学有一张包含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染色需要的最少颜色数。【输入样例】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【核心思想】问题分析给定一个每个结点度数均为2 22的无向图G GG即G GG由若干个不相交的环组成每个连通块是一个简单环。要求为结点染色使得相邻结点颜色不同求最少颜色数。这是一个图论性质分析 连通块分类问题核心在于利用每个结点度数为2 22的条件推导出图的结构特征进而确定每个连通块的色数。算法选择图结构分析度数为2 22的无向图必然由若干个简单环构成无重边、无自环保证环的色数判定偶环是二分图色数为2 22奇环不是二分图色数为3 33深度优先搜索DFS统计每个连通块的结点数判断奇偶性关键步骤建图读入n nn条边建立无向图的邻接表连通块遍历对每个未访问的结点i iic n t ← 0 cnt \leftarrow 0cnt←0启动d f s ( i ) dfs(i)dfs(i)统计连通块大小若c n t m o d 2 0 cnt \bmod 2 0cntmod20r e s ← 2 res \leftarrow 2res←2偶环二分图2 22色可染若c n t m o d 2 1 cnt \bmod 2 1cntmod21r e s ← 3 res \leftarrow 3res←3奇环非二分图需3 33色a n s ← max ⁡ ( a n s , r e s ) ans \leftarrow \max(ans, res)ans←max(ans,res)输出结果a n s ansans时间/空间复杂度时间复杂度O ( t ⋅ ( n m ) ) O ( t ⋅ n ) O(t \cdot (n m)) O(t \cdot n)O(t⋅(nm))O(t⋅n)其中m n m nmn每个结点度数为2 22DFS 遍历每个连通块一次空间复杂度O ( n ) O(n)O(n)邻接表和访问标记数组图论性质分析的核心思想度数约束推导结构无向图中所有结点度数为2 22且无重边、无自环则图必然由若干个不相交的简单环组成。每个连通块是一个环结点数等于边数二分图与色数偶环是二分图可以用2 22种颜色交替染色奇环包含奇数长度的回路不是二分图根据 Brooks 定理和具体结构分析需要3 33种颜色全局最优取最大整个图的最少颜色数等于所有连通块色数的最大值各连通块独立染色颜色可复用DFS 统计连通块利用访问标记数组和 DFS 遍历高效统计每个连通块的结点数无需显式找环适用于具有特殊度数约束的图结构分析、连通块分类判定类问题【算法标签】#普及 #DFS-图【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 常量最大结点数intt;// t: 数据组数intn;// n: 当前数据的结点数vectorintg[N];// g[x]: 结点 x 的邻接结点列表boolvis[N];// vis[x]: 标记结点 x 是否已被访问intcnt;// cnt: 当前连通块的结点数voiddfs(intx)// 深度优先搜索统计连通块大小{vis[x]true;// 标记当前结点已访问cnt;// 连通块结点数加一for(inti0;ig[x].size();i)// 遍历所有邻接结点{intyg[x][i];// y: 邻接结点if(vis[y])// 如果已访问跳过continue;dfs(y);// 递归搜索}}intmain(){cint;// 读入数据组数while(t--)// 循环处理每组数据{cinn;// 读入结点数for(inti1;in;i)// 清空邻接表g[i].clear();for(inti1;in;i)// 读入 n 条边{intu,v;// u, v: 边的两个端点cinuv;g[u].push_back(v);// 建立无向图g[v].push_back(u);}memset(vis,0,sizeof(vis));// 清空访问标记intans-1;// ans: 最少需要的颜色数intres;// res: 当前连通块需要的颜色数for(inti1;in;i)// 枚举每个结点处理所有连通块{cnt0;// 重置连通块计数器if(!vis[i])// 如果结点 i 未被访问新的连通块dfs(i);if(cnt%21)// 如果连通块结点数为奇数res3;// 奇环需要 3 种颜色else// 如果连通块结点数为偶数res2;// 偶环只需要 2 种颜色ansmax(ans,res);// 取所有连通块颜色数的最大值}coutansendl;// 输出最少需要的颜色数}return0;}【运行结果】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