【每日一题】7月9日题目精选—Color

活动时间：7月7日起至9月1日
活动内容：写满30篇每日一题的题解
活动奖励：即可额外获得牛客T恤一件
活动目的：滴滴滴～想充实的过完这个暑假嘛～快来写每日一题～每天都要进步喔～提升自己的同时还有超多福利喔～

每日一题交流群，群内定期有福利发放，群号：659028468

今日预告：
题号 NC14254
名称 Color
来源 Wannafly挑战赛1
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

颜色数就是最大度数，这个结论需要证明充分性（必要性是显然的），我们直接来看怎么构造，只要这么多个颜色一定能构造出来，充分性就得证了，构造的方法也出来了。
我们先拿最大度个颜色随便给边染色（从度数大的点连着的边开始染），如果一条边染不动了，出现的情况应该类似于用有6种颜色，当前这条边左点x别的边染上的颜色是1234，右点y的别的边染的是3456，这时如果我们要强行把当前z到y这个边的颜色染成5，那么y连出去的5那个边就要换一个颜色，比如说这个边是y到x',它换成了1，那么如果x连的点有1的边就需要再换掉，它可以换成5（因为刚刚，x’连的别的点有1的边就需要再换掉，它可以换成5（因为换掉之前y到x'的边是5，它又被换掉了，所有x'没有其他的5的边）以此类推一直找到没矛盾为止（相当于找增广路，原来5-1-5-1...的边变成了1-5-1-5...），这个操作类似于二分图匹配的匈牙利算法——用一个dfs，如果矛盾就继续往下搜给下面的边也换颜色即可。
（插入图1）

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目7月16日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴

提醒：更新昨天题解!
看完邓老师的题解，记得自己去做题提高呀~