解析

首先大胆猜结论：答案就是最大的点度数

考虑如何构造
设一个点联通的边的颜色集合为S，由题意得S中的元素不可重
假设新加入一条边(u,v)
设$c1=mex(S_u),c2=mex(S_v)$
如果c1等于c2，直接连就行了
否则，把这条边连成c1，看$S_v$中是否有c1，也就是是否产生矛盾
如果产生矛盾，v有一条连向x的颜色c1的边，就把这条边染成c2，再递归的看$S_x$中是否有c2…

一种类似于匈牙利的做法

为什么一定有解呢？
考虑什么时候无解
肯定是这个递归出现了自相矛盾的地方
比如一开始把（u，v）染成c1，递归回来又尝试把它染成c2
这就强人所难了
但是可以发现，由于我们尝试染的颜色是交替改变，所以自相矛盾产生的必要条件是出现奇环
众所周知，二分图的充要条件是没有奇环
得证

代码

代码利用异或的性质，实现十分优雅

#include<bits/stdc++.h> using namespace std; const int N=2050; const int mod=1e9+7; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,q; int u[N*100],v[N*100]; int du[N]; int col[N][N]; int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);n=read();m=read();q=read();for(int i=1;i<=q;i++){u[i]=read();v[i]=read()+n; du[u[i]]++;du[v[i]]++;}int ans(0);for(int i=1;i<=n+m;i++) ans=max(ans,du[i]);for(int i=1;i<=q;i++){//printf("--------i=%d\n",i);int x=u[i],y=v[i];int c1(1),c2(1);while(col[x][c1]) c1++;while(col[y][c2]) c2++;col[x][c1]=y;col[y][c2]=x;if(c1==c2) continue;for(int c=c2,now=y;now;now=col[now][c],c^=c1^c2){//printf("now=%d\n",now);swap(col[now][c1],col[now][c2]);}}printf("%d\n",ans);for(int i=1;i<=q;i++){for(int j=1;j<=ans;j++){if(col[u[i]][j]==v[i]){printf("%d ",j);break;}}}return 0; } /* */

总结

以上是生活随笔为你收集整理的CF600F：Edge coloring of bipartite graph（二分图、构造）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。