二分图边染色模板

Posted on | In

题目链接 https://ac.nowcoder.com/acm/problem/14254

题目大意：给一个二分图（n<=1e3，m<=2e3），要求对它的边进行染色，相邻边（即有公共点的边）不能是同一种颜色，问最少用多少种颜色（k）能完成染色任务，并输出一组可行解（每条边的颜色为1~k间的数）。

在图论中有一个Vizing定理：二分图边着色所需最小颜色数，等于图中点的最大度数。我们设当前需要在u和v之间加一条边，设u点尚未用过的最小的颜色编号是x，v点尚未用过的最小颜色编号是y。那么如果x=y，就直接令边(u,v)的颜色是x（y）即可；如果x<y，我们依然令(u,v)的颜色是x，然后让点v原有的颜色为x的边变色为y，接下来对于这条边连接的点v’，让它原有的颜色为y的边再变色为x……就这样一直修改下去，修改路径是一条从v出发，颜色依次是x、y、x……的边构成的路径（不会经过u）。
修改这条增广路的操作可以用dfs实现，复杂度是O（n）。在添加每条边的时候都有可能需要修改，所以整体复杂度O（mn）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

const int maxn=1001;

int es[maxn][maxn];
int color[maxn<<1];
typedef pair<int,int> pir;
map<pir,int> mp;

void dfs(int u,int v,int x,int y){
    int to=es[v][x];
    //把uv边从y色染成x色
    es[u][x]=v;es[v][x]=u;
    if(!to){
        //如果v之前没有x色的边
        es[v][y]=0;
    }else{
        dfs(v,to,y,x);
    }
}

int main(){
    int n,m,cur[2];
    cin>>n>>m;
    int ans=0;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        mp[pir(u,v)]=i;
        mp[pir(v,u)]=i;
        cur[0]=cur[1]=1;
        while(es[u][cur[0]])
            cur[0]++;
        while(es[v][cur[1]])
            cur[1]++;
        if(cur[0]>cur[1]){
            swap(u,v);swap(cur[0],cur[1]);
        }
        ans=max(ans,cur[1]);
        if(cur[0]==cur[1]){
            es[u][cur[0]]=v;
            es[v][cur[0]]=u;
        }else{
            dfs(u,v,cur[0],cur[1]);
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=ans;j++){
            int v=es[i][j];
            if(v){
                color[mp[pir(i,v)]]=j;
            }
        }
    }
    for(int i=1;i<=m;i++)
        cout<<color[i]<<endl;
}

/*
5 4
1 2
1 3
1 4
4 5
*/