CF600F Edge coloring of bipartite graph 题解

· · 题解

结论是颜色数为最大的点的度数。

必要性是显然的。

对于充分性，考虑构造一种方案。

坚持一个原则，尽量用没用过的颜色里面编号最小的。

每次加边 (u,v)，对于这两个点，设没用过的颜色最小为 C_u,C_v，严谨来说是 \operatorname{mex}。

如果 C_u=C_v，那么显然可以直接把这条边的颜色设为 C_u。

否则我们把边设为其中的任意一个颜色，假设你设为 C_u，那么 v 可能存在一条边 (v,x)=C_u，我们考虑把这条边染成 C_v，然后有冲突再更新....

这样一直更新就行了。

显然，我们是以 C_u,C_v,C_u,C_v,C_u,\cdots 这样交替染色的，所以不可能有环。

因为二分图有环长度必然是偶数，所以我们染的是 C_v，那么前置条件是那是路径的最后一个点 x 存在一条到达 u 的边颜色为 C_u，这与 u 原先没有颜色为 C_u 的边矛盾。

那为啥是最大的点的度数呢？

我们考虑每次相当于 u,v 各自多了一个颜色，其他点的颜色数不变，所以加完边之后恰好每个点的颜色都是度数。

时间复杂度为 \mathcal O((a+b)m)。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=2005;
const LL M=2e5+5;
LL A,B,m,ans,c[N][N],du[N],u[M],v[M];
int main()
{
    scanf("%lld%lld%lld",&A,&B,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&u[i],&v[i]);
        v[i]+=A;
        du[u[i]]++,du[v[i]]++;
    }
    LL ans=0;
    for(int i=1;i<=A+B;i++)ans=max(ans,du[i]);
    printf("%lld\n",ans);
    for(int i=1;i<=m;i++)
    {
        LL mx1=1,mx2=1;
        while(c[u[i]][mx1])++mx1;
        while(c[v[i]][mx2])++mx2;
        c[u[i]][mx1]=v[i],c[v[i]][mx2]=u[i];
        if(mx1==mx2)continue;
        for(LL t=mx2,x=v[i];x;x=c[x][t],t^=mx1^mx2)swap(c[x][mx1],c[x][mx2]);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=ans;j++)
        {
            if(c[u[i]][j]==v[i])
            {
                printf("%d ",j);
                break;
            }
        }
    }
}