题解：洛谷 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

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

相关推荐

AI-CRM如何重塑电子通信制造业销售与服务：从线索到现金的智能革命

TVA：具身智能技术生态的强力引擎（14）

Phigros高难度谱面技术解析：从动态判定线到音游玩家成长路径

更多资讯

nuclei-templates 实战教程：3 条命令跑通你的第一次漏洞扫描

LunaTranslator 游戏翻译上手：HOOK、OCR 与离线翻译，从安装到跑通

Mojo 项目 `max encode` 命令：将文本转换为 Embedding 向量

AM非相干解调仿真：包络检波与关键参数设置

Backstage v1.33.0-next.0 版本解析：CLI 破坏性变更、目录客户端请求分块与后端服务演进

Chrome侧边栏免安装投屏：WebUSB直连Android实现零配置投屏提单

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？