CF600F

· · 题解

Solution

算是一个经典结论了吧。

把一个二分图 (V_1,V_2,E) 每条边都进行染色，使得所有拥有公共点的两条边颜色都不一样，需要的最小颜色数是 \max_{u \in V_1 \cup V_2} \{ \deg u \}。很显然我们不能用更少的颜色实现这一目标。

而这个值能取到，使用构造法证明，顺带把这道题过了。

令 v = \max_{u \in V_1 \cup V_2} \{ \deg u \}。

考虑按顺序依次加边。假设我们目前需要确定颜色的边为 (u_1,u_2)。

如果 u_1 没有用过的颜色和 u_2 没有用过的颜色有非空交集，可以直接钦定当前这条边的颜色。

否则，假设 c 是 u_1 没有用过的颜色之一。那么考虑把这条边钦定成 c（下图中的红色）。那么根据设定，u_2 必定和另一个点 u_3 连了一条颜色为 c 的边。考虑更换这条边的颜色（图中的 CG）。我们可以随便再钦定一 u_2 没用过的颜色，比如说是 d（下图的黄色）。

注意，这时候因为 u_2 连上的边的数量小于 v，所以一定能找到这样一个 d。

这样会引起一连串连锁反应。不过没关系，我们在图上不断走红黄交错的边。很容易注意到，我们永远不会得到环，因为根据设定，u_2 没有连 d 边。

那我们把这条极长的，红黄交错的路径全部翻转颜色（也就是红变黄，黄变红）即可。是不是很像找增广路？不过不完全一样就是了。

复杂度 O(nm)，可以认为是 O(n^3)。

脑筋急转弯：如果是把二分图的点染色，让每条边连的两个点颜色不同怎么办？答案是 2（当然不考虑有一半是空集的情况。）

代码（非递归找环版）：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1000+10,MAXM=1e5+10;
int n1,n2,m,lst,degl[MAXN],degr[MAXN],x[MAXM],y[MAXM],res[MAXM],id[MAXN][MAXN],tl[MAXN][MAXN],tr[MAXN][MAXN];
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n1>>n2>>m;
    ffor(i,1,m) cin>>x[i]>>y[i],id[x[i]][y[i]]=i,degl[x[i]]++,degr[y[i]]++;
    lst=max(*max_element(degl+1,degl+n1+1),*max_element(degr+1,degr+n2+1));
    ffor(i,1,m) {
        int u1=x[i],u2=y[i],flg=0;
        ffor(j,1,lst) if(tl[u1][j]+tr[u2][j]==0) flg=j;
        if(flg) tl[u1][flg]=u2,tr[u2][flg]=u1;
        else {
            int flg1=0,flg2=0;
            ffor(j,1,lst) if(tl[u1][j]==0) flg1=j;
            ffor(j,1,lst) if(tr[u2][j]==0) flg2=j;  
            vector<int> cl,cr;
            int pos=u2;
            while(pos) {
                cr.push_back(pos);
                if(tr[pos][flg1]) {
                    cl.push_back(tr[pos][flg1]);
                    pos=tl[tr[pos][flg1]][flg2];
                }
                else break ;
            }
            for(auto id:cl) swap(tl[id][flg1],tl[id][flg2]);
            for(auto id:cr) swap(tr[id][flg1],tr[id][flg2]);
            tl[u1][flg1]=u2,tr[u2][flg1]=u1;
        }
    }
    ffor(i,1,n1) ffor(j,1,lst) res[id[i][tl[i][j]]]=j;
    cout<<lst<<'\n';
    ffor(i,1,m) cout<<res[i]<<' ';
    return 0;
}