coloring.cc

#include <iostream>
#include <boost/dynamic_bitset.hpp>
#include <stdlib.h>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>

#define LEN 10000

int min_degree_vertex(std::vector<std::vector<int> >& g,  boost::dynamic_bitset<> s) {
  int const n = g.size();
  int x = -1;
  int x_d = (1 << 30);
  for (boost::dynamic_bitset<>::size_type u = s.find_first();
       u != s.npos;
       u = s.find_next(u)) {
    int u_d = 0;
    for (auto v : g[u]) {
      if (s[v] == true) {
	u_d += 1;
      }
    }
    if (u_d < x_d) {
      x = u;
      x_d = u_d;
    }
  }
  return x;
}

// 頂点 x に隣接する頂点の集合と x 自身だけからなる集合の和集合
// N[x] = N(x) \cup { x } を返す
std::vector<int> neighbour(std::vector<std::vector<int> >& g, boost::dynamic_bitset<> s, int x) {
  std::vector<int> nx;
  // x 自身をまずは追加
  nx.push_back(x);
  for (auto y : g[x]) {
    if (s[y] == true) {
      nx.push_back(y);
    }
  }
  return nx;
}

// g[s] の極大独立集合の集合（リスト）を L に入れる
void miss(std::vector<std::vector<int> >& g, boost::dynamic_bitset<> s, std::vector<int>* res, std::set<std::set<int> >* L) {
  // s = {} なら，G[s] の極大独立集合は {} 
  if (s.count() == 0) {
    std::set<int> M;
    for (auto x : *res) {
      M.insert(x);
    }
    L->insert(M);
    return;
  }

  // 次数最小の頂点 x を探索
  int x = min_degree_vertex(g, s);
  
  // N[x] = N(x) \cup { x } を計算
  std::vector<int> nx = neighbour(g, s, x);

  // N[x] に属する各頂点 y について処理
  for (auto y : nx) {
    // t = s \ N[y] を計算
    boost::dynamic_bitset<> t = s;
    // std::cout << "t = " << t << std::endl;
    std::vector<int> ny = neighbour(g, s, y);
    for (auto z : ny) {
      t.reset(z);
    }
    res->push_back(y);
    miss(g, t, res, L);
    res->pop_back();
  }
  return;
}

std::unordered_map<boost::dynamic_bitset<>,
		   std::vector<std::set<int >> > hash;

std::unordered_map<boost::dynamic_bitset<>,
		   std::set<std::set<int >> > MIS;


std::vector<std::set<int> > coloring_sub(std::vector<std::vector<int> >& g, boost::dynamic_bitset<> X, int l) {
  // 既に計算済みの集合（誘導部分グラフ）ならその分割を返す
  if (hash.count(X) != 0) {
    return hash[X];
  }
  
  // X が空集合なら，その誘導部分グラフに対する分割も空集合
  if (X.count() == 0) {
    std::vector<std::set<int> > v;
    return v;
  }

  // mis に g[X] の極大部分集合の集合を入れる
  std::set<std::set<int> > mis;
  if (MIS.count(X) != 0) {
    mis = MIS[X];
  } else {
    std::vector<int> v;
    miss(g, X, &v, &mis);
    MIS[X] = mis;
  }

  // X の分割のサイズは高々 n であるため，
  // それより大きい値 n+1 で最適値 opt_val を初期化
  // 分割のサイズが最小となる最適な分割 OPT も NULL で初期化
  int const n = g.size();
  int opt_val = n+1;
  std::vector<std::set<int> > OPT;
  for (auto I : mis) {
    // g[X] の極大独立集合 I を X から取り除いた集合 Y = X\I の分割を再帰的に計算
    boost::dynamic_bitset<> Y = X;
    for (auto i : I) {
      Y.reset(i);
    }

    // Y = X\I での最適な分割を計算
    std::vector<std::set<int> > L = coloring_sub(g, Y, l+1);
    if (L.empty()) {
      // Y = X \cup I = {} であり，X の最適な分割は { I }
      std::vector<std::set<int> > C;
      C.push_back(I);
      return C;
    }
    if (L.size() + 1 < opt_val) {
      // X の分割のサイズ（g[X]の彩色数）が現時点の候補 opt_val よりも小さかったら
      // X の分割 OPT を更新
      opt_val = L.size() + 1;
      OPT = L;
      OPT.push_back(I);
    }
  }

  hash[X] = OPT;    
  return OPT;
}

// 各頂点に何色を塗るか（整数を割当てるか）を配列 A で表現
// 配列 A を返す
std::vector<int> coloring(std::vector<std::vector<int> > g, int n) {
  boost::dynamic_bitset<> s(n);
  s.set();

  // 第 4 引数は再帰の深さを表すものでデバッグ用
  // 誘導部分グラフ G[s] の最小頂点彩色に対応する s の分割を返す
  // i と j に同じ色を塗ることは i と j が（分割の）同じ集合に属することに対応
  std::vector<std::set<int> > S = coloring_sub(g, s, 0);
  std::vector<int> A(n);

  // 得られた分割に沿って頂点に色を塗る
  unsigned color = 1;
  for (auto s : S) {
    for (auto x : s) {
      A[x] = color;
    }
    ++color;
  }

  return A;
}

int main()
{
  char buf[LEN];
  while (1) {
    fgets(buf, LEN, stdin);
    if (buf[0] == 'c') {
      continue;
    }
    if (buf[0] == 'p') {
      break;
    }
  }

  int n, m;
  char tmp[LEN];
  sscanf(buf, "p %s %d %d\n", tmp, &n, &m);
  std::vector<std::vector<int> > g(n);

  for (int i = 0; i < m; ++i) {
    int u, v;
    fscanf(stdin, "e %d %d\n", &u, &v);
    g[u-1].push_back(v-1);
    g[v-1].push_back(u-1);
  }

  std::vector<int> A = coloring(g, n);
  
  for (int i = 0; i < n; ++i) {
    printf("%d ", A[i]);
  }
  putchar('\n');
  return 0;
}