xlpg0713 二分图边染色摘抄

二分图边染色

给定一张二分图，你需要把边染色，使得颜色数尽量少。

复杂度 $nm$ 。

首先可以证明答案是 $\max \deg$ ，我们给出一个构造性证明（算法流程）：

顺序确定每条边的颜色，设当前枚举到 $(u,v)$ ，找到 $\text{mex } S_u,\text{mex }S_v$ ，记作 $a_u,a_v$ 。

若 $a_u=a_v$ ，则直接染色为 $a_u$ 。

否则，不妨钦定 $a_u<a_v$ ，我们从 $v$ 那边找一个 $a_u,a_v$ 交替出现的极长增广路，然后反转颜色，这一定不会连到 $u$ ，即使 $u$ 练出了 $a_v$ 。

不妨假设 $u$ 是左部点，那么一个左部点被找上必然有 $a_u$ 从右边连过来，所以不会被连到。

做完这个过程后将该边染色为 $a_u$ 。

由于每次连的边的颜色都 $\in[0,\deg u)$ ，所以这个过程是对的。