[Codeforces 600F]Edge coloring of bipartite graph

我們可以構造一個演算法，讓使用的顏色數量=最少顏色數量 (也就是點的最大度數)

可以將邊一條一條的慢慢著色
如果存在顏色$c_{0}$，讓這條邊連到的兩點 (假設連到$v_{0}$和$v_{1}$) 都沒有連到其他顏色$c_{0}$的邊，那把這條邊塗上$c_{0}$就完成了
否則，找個還沒覆蓋$v_{0}$的顏色$c_{0}$、還沒覆蓋$v_{1}$的顏色$c_{1}$，將$v_{1}$連到的那個顏色是$c_{0}$的邊 (假設連到$v_{1}$和$v_{2}$) 塗上$c_{1}$，那麼$v_{0}$和$v_{1}$之間的邊就可以塗成$c_{0}$了
如果這時$v_{2}$又有另一條顏色$c_{1}$的邊 (假設連到$v_{2}$和$v_{3}$)，那就把這條邊塗成$c_{0}$
如果這時$v_{3}$又有另一條顏色$c_{0}$的邊 (假設連到$v_{3}$和$v_{4}$)，那就把這條邊塗成$c_{1}$
如果這時$v_{4}$又有另一條顏色$c_{1}$的邊 (假設連到$v_{4}$和$v_{5}$)，那就把這條邊塗成$c_{0}$
......

仔細推敲就可以發現，因為是二分圖，顏色又是$c_{0}$和$c_{1}$交錯，因此形成一個環把顏色塗回來的情況是不可能發生的！
也就是說，這個演算法在$N$次著色內會結束

知道怎麼做了吧^_^

實作上就會出現小麻煩了，不過相信大家應該都會自己debug，詳情請看我的code XD

時間複雜度：$O(MN\log N)$ (其中map可以用陣列取代去掉一個$\log$)

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<map>
#include<set>
using namespace std;
void getmax(int &a,const int b){if(b>a)a=b;}
struct Edge
{
    int a,b,color;
    Edge(){}
    Edge(const int _a,const int _b,const int _color):a(_a),b(_b),color(_color){}
};
vector<Edge>EDGE;
int A,N,M,K;
vector<int>ET[2000];
map<int,int>COLOR[2000];
set<int>REMAIN[2000];
void Uncolor(const int u,const int color)
{
    if(color==-1)return;
    auto it=COLOR[u].find(color);
    assert(it!=COLOR[u].end());
    COLOR[u].erase(it);
    REMAIN[u].insert(color);
    assert((int)(COLOR[u].size()+REMAIN[u].size())==K);
}
void Color(const int u,const int color,const int ei)
{
//    if(COLOR[u].find(color)!=COLOR[u].end())printf("u=%d,color=%d,ei=%d(%d,%d)\n",u,color,ei,EDGE[ei].a,EDGE[ei].b);
    assert(COLOR[u].find(color)==COLOR[u].end());
    auto it=REMAIN[u].find(color);
    assert(it!=REMAIN[u].end());
    COLOR[u][color]=ei;
    REMAIN[u].erase(it);
    assert((int)(COLOR[u].size()+REMAIN[u].size())==K);
}
int FindColor(const int a,const int ei,const int except)
{
    const int b=(a==EDGE[ei].a?EDGE[ei].b:EDGE[ei].a);
    for(const int c:REMAIN[a])if(c!=except&&REMAIN[b].find(c)!=REMAIN[b].end())return c;
    for(const int c:REMAIN[a])if(c!=except)return c;
    assert(0);return -1;
}
void ColorEdge(const int u,const int ei,const int color)
{
    const Edge &e=EDGE[ei];
    const int pre_color=e.color;
    if(pre_color==color)return;
    EDGE[ei].color=color;
    Uncolor(u,pre_color);
    Color(u,color,ei);
    const int nxt=(u==e.a?e.b:e.a);
//    printf("(%d,%d)\n",u,nxt);
    if(true)
    {
        Uncolor(nxt,pre_color);
        auto it=COLOR[nxt].find(color);
        if(it!=COLOR[nxt].end())
        {
            const int nxtei=it->second;
//            assert(EDGE[nxtei].color==color&&*REMAIN[nxt].begin()!=color);
            ColorEdge(nxt,nxtei,pre_color!=-1?pre_color:FindColor(nxt,nxtei,color));
//            if(COLOR[nxt].find(color)!=COLOR[nxt].end())printf("nxt=%d,nxtei=%d(%d,%d),now=%d(%d,%d)\n",nxt,nxtei,EDGE[nxtei].a,EDGE[nxtei].b,COLOR[nxt][color],EDGE[COLOR[nxt][color]].a,EDGE[COLOR[nxt][color]].b);
        }
        Color(nxt,color,ei);
    }
}
void ColorVertex(const int u)
{
    for(const int ei:ET[u])if(EDGE[ei].color==-1)ColorEdge(u,ei,FindColor(u,ei,-1));
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&A,&N,&M),N+=A;
    for(int i=0;i<N;i++)ET[i].clear(),COLOR[i].clear(),REMAIN[i].clear();
    for(int i=0,a,b;i<M;i++)
    {
        scanf("%d%d",&a,&b),a--,b--,b+=A;
        EDGE.push_back(Edge(a,b,-1));
        ET[a].push_back(i),ET[b].push_back(i);
    }
    K=0;
    for(int i=0;i<N;i++)getmax(K,(int)ET[i].size());
    for(int i=0;i<N;i++)for(int c=0;c<K;c++)REMAIN[i].insert(c);
    for(int i=0;i<N;i++)ColorVertex(i);
    printf("%d\n",K);
    assert(M==(int)EDGE.size());
    for(int i=0;i<M;i++)
    {
        if(i)putchar(' ');
        printf("%d",EDGE[i].color+1);
    }
    puts("");
    return 0;
}