Codeforces ECR #002 : F. Edge coloring of bipartite graph

わかれば簡単なんだけどね…。
http://codeforces.com/contest/600/problem/F

問題

A個の頂点群とB個の頂点群を結ぶM無向辺からなる二部グラフが与えられる。
これらの辺を、同じ点を端点にする辺同士が同じ色にならないように色分けしたい。
最小の色数を求め、また色分け例を示せ。

解法

Editorialを見て回答。

おおよそ推測付く通り、最小の色数は頂点の次数の最大値。
後はどう色分けしていくかの問題となる。

各頂点において、その点を端点としている辺が使った色の番号と、その番号に対応する接続先頂点を覚えておこう。
最大次数＝最大色数をDとし、このグラフに順に1辺ずつ追加しながら色を塗ることを考える。

ここで点の対(x,y)を結ぶ辺に色を塗るとする。
D色のうちどちらでも使われてない色があれば、その色で塗ればよい。
もしそのような色がない場合、最大次数がDより(x,y)に辺を結ぶ前はx,yはそれぞれ次数は(D-1)以下なので以下のような色c1,c2が必ず1つ以上見つかる。

• 色c1 : 点xを結ぶ辺では使っているが、点yを結ぶ辺では使っていない
• 色c2 : 点yを結ぶ辺では使っているが、点xを結ぶ辺では使っていない

ここで、点yを結ぶ辺から色c2を消すことが出来れば、(x,y)の間を結ぶ辺に色c2を割り当てることができる。
そこで、点yで使われてない色c1を使う代わりに、色c2を使わないようにすることを考える。
そのためには、色c2を使う辺を(z,y)としたとき、(z,y)の間を色c1で塗れば色c2が空く。
ただしそのためには、点zで色c1を使わないようにしてもらわなければならない。

…この作業を繰り返すと、「この色を使っていいから、代わりにこの色を空ける」という処理を再帰的に繰り返せばよいことになる。
この探索は、頂点数O(A+B)繰り返すうちに必ず落ち着く。
またグラフが二部グラフになっているため、無限に探索することはない。

int A,B,M;
int X[101010],Y[101010];
int used[2010][2010];
int in[2010];
int C;
int ret[2020][2020];

void gofree(int v,int tofree,int okc) {
	int tar=used[v][tofree];
	if(tar!=-1) {
		used[v][tofree]=-1;
		used[tar][tofree]=-1;
		gofree(tar,okc,tofree);
		used[v][okc]=tar;
		used[tar][okc]=v;
		ret[min(v,tar)][max(v,tar)]=okc;
	}
	return;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(used);
	
	cin>>A>>B>>M;
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		X[i]--, Y[i]--;
		Y[i]+=A;
		C=max(C,++in[X[i]]);
		C=max(C,++in[Y[i]]);
		
		int c1=-1,c2=-1;
		FOR(y,C) {
			if(c1==-1 && used[X[i]][y]>=0 && used[Y[i]][y]==-1) c1=y;
			if(c2==-1 && used[X[i]][y]==-1 && used[Y[i]][y]>=0) c2=y;
			if(used[X[i]][y]==-1 && used[Y[i]][y]==-1) break;
		}
		
		if(y>=C) {
			gofree(Y[i],c2,c1);
			y=c2;
		}
		ret[X[i]][Y[i]]=y;
		used[X[i]][y]=Y[i];
		used[Y[i]][y]=X[i];
	}
	
	cout<<C<<endl;
	FOR(i,M) cout<<(ret[X[i]][Y[i]]+1)<<" ";
	cout<<endl;
}

まとめ

言われてみるとシンプルな解法だね。