勉強したことのメモ書きを残しておきます
catupperさんのこの資料を読んで勉強しました。
www.slideshare.net
二部グラフの辺彩色については具体的に12ページから述べられています。
Konigの定理
- 任意の二部グラフの辺彩色数は二部グラフの最大次数Dに一致する。
証明を追っていきます。最大次数がDでグラフの辺の数がN未満のグラフについてこの定理の成立を仮定して帰納的に示します。(辺数がDの時命題は自明に成立)
最大次数がDで辺数がNのグラフGについて一つの辺eを選びます。その辺を取り除いたグラフG'の最大次数はDとします。この時仮定よりグラフG'はD色で辺彩色可能です。
辺eが頂点XとYを結んでいるとします。この時頂点X,Yの次数はD-1以下よりどちらの頂点にも使われてない色が存在します。Xにおいて使われていない色をs,Yにおいて使われていない色をtとします。
- sとtが一致する時→辺eをsで塗ってしまって問題ない
- sとtが一致しない時→この場合について以下で考える
この時Xから始まる、色がt→s→t→s…となる最大のパスを探します。
このパスはDFSで容易に求めることができます(辺彩色の定義よりある頂点についてsまたはtで塗られている辺は高々1本なので)
またこのパスがYを経由しないことも示します。二部グラフよりYに至るパスはsでなくtでないといけないが、Yにおいてtは使われてない仮定に矛盾。よってこのパスはY以外の頂点Zで終わる。
このパスについてtとsの色を入れ替えることを考えます。パスの途中の頂点はsとt両方の辺を使っているので入れ替えても問題は生じません。また終点Zはパスの最大性より片方の色の辺が存在していないので入れ替えても辺彩色が可能です。
こうして辺の色を入れ替えたグラフでは辺eがtで辺彩色可能です。こうして最大次数がDでグラフの辺の数がNのグラフについて命題が成立することが示され、帰納的に元の命題が成立することが示されます。
Educational Codeforces Round 2 F.Edge coloring of bipartite graph
昔のECRにこの話が丸々出ていたのでこの問題を紹介します。
上で述べたことをそのまま実装したらできました。
計算量はO(NM)で抑えられているはずです（辺毎に毎回DFSする場合が最悪パターン）が、実際はそのような場合が存在しないので実際は更に早く動くことが想定されます。
以下実装です。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;
const int MMAX=1e5+5;
int a,b,m;
int e_id[2020][2020];
int deg[2020];
int dmax=0;
int col[2020][1010];
int ans[MMAX];
pair<int,int> E[MMAX];
bool paint(int x,int y){
for(int i=0;i<dmax;i++){
if(col[x][i]<0&&col[y][i]<0){
ans[e_id[x][y]]=i;
col[x][i]=e_id[x][y];
col[y][i]=e_id[x][y];
return true;
}
}
return false;
}
void dfs(int v,int s,int t,int dep){
if(col[v][s]<0){
col[v][t]=-1;
return;
}
int x=E[col[v][s]].first,y=E[col[v][s]].second;
if(v==x)swap(x,y);
dfs(x,t,s,dep+1);
ans[e_id[v][x]]=t;
col[v][t]=e_id[v][x];
col[x][t]=e_id[v][x];
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> a >> b >> m;
for(int i=0;i<m;i++){
int x,y; cin >> x >> y;
--x; --y; y+=a;
e_id[x][y]=e_id[y][x]=i;
E[i]={x,y};
deg[x]++;
deg[y]++;
}
for(int i=0;i<a+b;i++){
dmax=max(dmax,deg[i]);
}
for(int i=0;i<a+b;i++){
for(int j=0;j<dmax;j++){
col[i][j]=-1;
}
}
for(int i=0;i<m;i++){
if(!paint(E[i].first,E[i].second)){
int x=E[i].first,y=E[i].second;
int s=0,t=0;
while(col[x][s]>=0)s++;
while(col[y][t]>=0)t++;
dfs(x,t,s,0);
col[x][t]=i;
col[y][t]=i;
ans[i]=t;
}
}
cout << dmax << endl;
for(int i=0;i<m;i++){
cout << ans[i]+1 << " ";
}
cout << endl;
}
