根据 Vizing 定理，最小的答案就是二分图的最大度数。同时可以在 \(O(nm)\) 的时间复杂度内构造出一组解。
显然对于这道题我们需要更高效的做法。注意到 \(2\) 的整数次幂，考虑分治。
既然答案跟最大度数有关，如果我们每次能把边集分为两个集合，认为她们的颜色本质不同，且使得每个点的出边在两个集合中的个数相差不超过 \(1\)。然后对于对于这两个集合分别分治下去，就一定能用不超过 \(2^{\left \lceil \log d \right \rceil }\) 种颜色给边染色，其中 \(d\) 是最大度数，而这也正是题目给的限制 \(X\)。
现在考虑如何划分这连个集合。（实际上和 这道题 有异曲同工之妙。
我们套路地给无向边定向，这样对于每个点的连边我们可以通过出边和入边将其分为两类，此时目标即等价于对于每个节点其入度和出度相差不超过 \(1\)。
看上去很像欧拉回路（欧拉回路要求每个点出入度相等，且其存在的充要条件是每个点度数均为偶数）。我们考虑对于每个度数为奇数的点与超级源点连一条边，同时由于度数为奇数的点的个数一定是偶数，所以整张图一定可以找出若干条欧拉回路（因为可能不连通）。此时我们再把与超级源点的连边撤去，发现每个节点都满足入度和出度相差不超过 \(1\)。
递归每层找欧拉回路的时间复杂度是 \(O(m)\)，至此我们在 \(O(m \log d)\) 的时间复杂度内解决了这个问题。
标签：度数,每个,题解,复杂度,ar,2018,回路,集合,欧拉 From： https://www.cnblogs.com/CloudWings/p/18486984