二部グラフの辺彩色

説明

二部グラフの辺彩色は最大マッチングを繰り返し行うことで求めることができる．

計算量

多分 O(L^2 R E)，ただし L, R は左右の頂点，E は辺数．

使い方

const graph& g

二部グラフ．0 ... L-1 が左側頂点，L ... g.size()-1 が右側頂点に対応する．

int L

二部グラフの左側の頂点の数．

vector< vector<int> > color

color[i][j] は辺(i,j)の色．0 は非マッチを表す．

ソースコード

bool augment(vector< vector<int> > &C, int u, int c1, int c2) {
  int v = C[u][c1];
  if (v >= 0) {
    augment(C, v, c2, c1);
    C[v][c2] = u;
    C[u][c1] = -1;
  }
  C[u][c2] = v;
}
int bipartiteColouring(const Graph &g,
    int L, vector< vector<int> > &color) {
  int n = g.size(), deg = 0;
  REP(u, n) deg = max(deg, (int)g[u].size());
  vector< vector<int> > C(n, vector<int>(deg, -1));

  REP(u,L) FOR(e,g[u]) {
    int v = e->dst, cu = 0, cv = 0;
    while (C[u][cu] != -1) ++cu;
    while (C[v][cv] != -1) ++cv;
    if (cu != cv) augment(C, v, cu, cv);
    C[u][cu] = v; C[v][cu] = u;
  }
  color.assign(n, vector<int>(n)); // make explicit color-table
  REP(u, L) REP(c, deg) if (C[u][c] >= 0)
    color[u][C[u][c]] = c+1;
  return deg;
}

Verified

• UVA 10615 (Rook), 348 MS