color.c

// 彩色数最小の頂点彩色を求めるプログラム

#include <stdio.h>
#include <stdlib.h>

#define LEN 10000
#define HSIZE (1 << 17) // ハッシュテーブルのサイズ

typedef struct PAIR {
  int fst;
  int snd;
} pair;

typedef struct LNODE {
  int val;
  struct LNODE* next;
} lnode;

typedef struct LIST {
  int size;
  lnode* head;
} list;

void push(list* l, int x) {
  lnode* tmp = (lnode*)calloc(1, sizeof(lnode));
  tmp->val = x;
  if (l->head != NULL) {
    tmp->next = l->head;
  }
  l->head = tmp;
  l->size += 1;
}

void push_u(list* l, int x) {
  for (lnode* p = l->head; p != NULL; p = p->next) {
    if (x == p->val) {
      return;
    }
  }
  
  lnode* tmp = (lnode*)calloc(1, sizeof(lnode));
  tmp->val = x;
  if (l->head != NULL) {
    tmp->next = l->head;
  }
  l->head = tmp;
  l->size += 1;
}

int delete(list* l, int x) {
  if (l == NULL || l->size == 0) {
    return -1;
  }
  lnode *p, *q;
  if (l->head->val == x) {
    p = l->head;
    l->head = l->head->next;
    free(p);
    l->size -= 1;
    return 0;
  }
  for (p = l->head; p != NULL; ) {
    q = p;
    p = p->next;
    if (p != NULL && p->val == x) {
      q->next = p->next;
      l->size -= 1;
      free(p);
      return 0;
    }
  }
  return -1;
}

void clear(list* l) {
  if (l == NULL) {
    return;
  }
  lnode *p, *q;
  for (p = l->head; p != NULL; ) {
    q = p;
    p = p->next;
    free(q);
  }
  l->size = 0;
  l->head = NULL;
}

void list_print(list* l) {
  if (l == NULL) {
    return;
  }
  for (lnode* p = l->head; p != NULL; p = p->next) {
    printf("%d ", p->val);
  }
}

typedef struct UNODE {
  unsigned long val;
  struct UNODE* next;
} unode;

typedef struct ULIST {
  int size;
  unode* head;
} ulist;


void upush(ulist* l, unsigned long x) {
  unode* tmp = (unode*)calloc(1, sizeof(unode));
  tmp->val = x;
  if (l->head != NULL) {
    tmp->next = l->head;
  }
  l->head = tmp;
  l->size += 1;
}

void upush_unique(ulist* l, unsigned long x) {
  for (unode* p = l->head; p != NULL; p = p->next) {
    if (x == p->val) {
      return;
    }
  }
  
  unode* tmp = (unode*)calloc(1, sizeof(unode));
  tmp->val = x;
  if (l->head != NULL) {
    tmp->next = l->head;
  }
  l->head = tmp;
  l->size += 1;
}

int udelete(ulist* l, unsigned long x) {
  if (l == NULL || l->size == 0) {
    return -1;
  }
  unode *p, *q;
  if (l->head->val == x) {
    p = l->head;
    l->head = l->head->next;
    free(p);
    l->size -= 1;
    return 0;
  }
  for (p = l->head; p != NULL; ) {
    q = p;
    p = p->next;
    if (p != NULL && p->val == x) {
      q->next = p->next;
      l->size -= 1;
      free(p);
      return 0;
    }
  }
  return -1;
}

void uclear(ulist* l) {
  if (l == NULL) {
    return;
  }
  unode *p, *q;
  for (p = l->head; p != NULL; ) {
    q = p;
    p = p->next;
    free(q);
  }
  l->size = 0;
  l->head = NULL;
}

ulist* ulist_copy(ulist* X) {
  if (X == NULL) {
    return NULL;
  }
  ulist* Y = (ulist*)calloc(1, sizeof(ulist));
  for (unode* p = X->head; p != NULL; p = p->next) {
    upush(Y, p->val);
  }
  return Y;
}

// L が x を含めば 0 を返し，含まなければ -1 を返す．
int ulist_contain(ulist* L, unsigned long x) {
  for (unode* p = L->head; p != NULL; p = p->next) {
    if (p->val == x) {
      return 0;
    }
  }
  return -1;
}

// X と Y が同じ要素を持つリストならば 0 を返す．
// そうでなければ -1 を返す．
int ulist_equiv(ulist* X, ulist* Y) {
  for (unode* p = X->head; p != NULL; p = p->next) {
    if (ulist_contain(Y, p->val) == -1) {
      return -1;
    }
  }
  return 0;
}

void ulist_print(ulist* l) {
  if (l == NULL) {
    return;
  }
  for (unode* p = l->head; p != NULL; p = p->next) {
    printf("%lu ", p->val);
  }
}

// ハッシュテーブルのセル
typedef struct HCELL {
  unsigned long key;
  ulist* family;
} hcell;

// ハッシュテーブル
hcell COLOR[HSIZE];
hcell MIS[HSIZE];

unsigned long h1(unsigned long X) {
  return X;
}

unsigned long h2(unsigned long X) {
  return X + 1;
}

// ハッシュ関数（ダブルハッシュ）
unsigned long hash_function(unsigned long X, int i) {
  return (h1(X) + i * h2(X)) % HSIZE;
}

// ハッシュテーブル H にキーを X として集合族 f を挿入
// COLOR の場合は g[X] に対する分割をメモ
// MIS   の場合は g[X] に対する極大独立集合の集合をメモ
void hash_insert(hcell* H, unsigned long X, ulist* f) {
  for (int i = 0; i < HSIZE; ++i) {
    unsigned long j = hash_function(X, i);
    if (H[j].family == NULL) {
      H[j].key = X;
      H[j].family = ulist_copy(f);
      return;
    }
  }
  fprintf(stderr, "ERROR: Hash table is full.\n");
  exit(1);
}

// 集合族 f がハッシュテーブルに入っていれば，そのセルの番地を返す．
// 入っていなければ -1 を返す．
int hash_search(hcell* H, unsigned long X) {
  for (int i = 0; i < HSIZE; ++i) {
    int j = hash_function(X, i);
    if (H[j].family != NULL && H[j].key == X) {
      return j;
    }
  }
  return -1;
}

void hash_clear(hcell* H) {
  for (int i = 0; i < HSIZE; ++i) {
    if (H[i].family != NULL) {
      uclear(H[i].family);
    }
  }
}

unsigned count_bits(unsigned long s) {
  unsigned count = 0;
  while (s > 0) {
    if ((s & 1) == 1) {
      ++count;
    }
    s = s >> 1;
  }
  return count;
}

int min_degree_vertex2(list* g, int n, unsigned long s) {
  int x = -1;
  int p = 0;
  for ( ; p < n; ++p) {
    if ((s & (1ULL << p)) != 0) {
      x = p;
      break;
    }
  }
  int x_d = 0;
  for (lnode* q = g[x].head; q != NULL; q = q->next) {
    if (((1ULL << q->val) & s) != 0) {
      ++x_d;
    }
  }
  for (++p; p < n; ++p) {
    if ((s & (1ULL << p)) == 1) {
      int tmp_d = 0;
      int y = p;
      for (lnode* q = g[y].head; q != NULL; q = q->next) {
	if (((1ULL << q->val) & s) != 0) {
	  ++tmp_d;
	}
      }
      if (tmp_d < x_d) {
	x = y;
	x_d = tmp_d;
      }
    }
  }
  return x;
}

// 頂点 x に隣接する頂点の集合と x 自身だけからなる集合の和集合
// N[x] = N(x) \cup { x } を返す
unsigned long neighbour2(list* g, unsigned long s, unsigned long x) {
  // x 自身をまずは追加
  unsigned long nx = (1ULL << x);
  for (lnode* p = g[x].head; p != NULL; p = p->next) {
    unsigned long y = p->val;
    // 隣接リストをなめて隣接する頂点 y も追加
    // ただし，y が G[s] の中に残っている頂点であるかも確認
    if ((s & (1ULL << y)) != 0) {
      nx |= (1ULL << y);
    }
  }
  return nx;
}


// enumerate maximal independent set
int level;
void print_mis(list* g, unsigned long n, unsigned long s, unsigned long res) {
  if (count_bits(s) == 0) {
    return;
  }

  // 最小次数の頂点を探索
  // この処理は必要？ どの頂点を選んでも同じ？
  //  -> おそらく |N[x]| が最小のものを選ぶべき
  unsigned long x = min_degree_vertex2(g, n, s);
  unsigned long nx = neighbour2(g, s, x);

  for (unsigned long p = 0; p < n; ++p) {
    unsigned long t = s;
    if ((nx & (1ULL << p)) != 0) {
      unsigned long y = p;
      // s \ N[y]
      unsigned long ny = neighbour2(g, s, y);
      t |= ny;
      t -= ny;

      unsigned long tmp = res;
      res += (1ULL << y);
      ++level;
      print_mis(g, n, t, res);
      res = tmp;
      --level;
    }
  }
  return;
}

// g[s] の極大独立集合の集合（リスト）を L に入れる
// L の各要素は整数で，集合を整数（ビット列）で表している
void miss(list* g, unsigned long n, unsigned long s, unsigned long res, ulist* L) {
  // s = {} なら，G[s] の極大独立集合は {} 
  if (count_bits(s) == 0) {
    upush_unique(L, res);
    return;
  }

  // 次数最小の頂点 x を探索
  /*
   * この処理は必要？ どの頂点を選んでも同じ？
   * -> おそらく |N[x]| が最小のものを選ぶべき
   */
  unsigned long x = min_degree_vertex2(g, n, s);
  // N[x] = N(x) \cup { x } を計算
  unsigned long nx = neighbour2(g, s, x);

  for (unsigned long p = 0; p < n; ++p) {
    // N[x] に属する各頂点 y について処理
    if ((nx & (1ULL << p)) != 0) {
      unsigned long t = s;
      unsigned long y = p;
      // t = s \ N[y] を計算
      unsigned long ny = neighbour2(g, s, y);
      t |= ny;
      t -= ny;

      unsigned long tmp = res;  // res の値を保存
      res |= (1ULL << y);       // res に y を追加
      ++level;   // 再帰の深さを表すデバッグ用の変数
      miss(g, n, t, res, L);    // t = s\y の誘導部分グラフに対する極大独立集合 res を再帰的に計算
      res = tmp; // 再帰から戻ってきて res の値を復元
      --level;
    }
  }
  return;
}

void print_set(unsigned long s) {
  printf("{");
  for (unsigned i = 0; s > 0; ++i, s = s >> 1) {
    if ((s & 1) == 1) {
      printf(" %u", i+1);
    }
  }
  printf( " }\n");
}

void print_family(ulist* L) {
  for (unode* p = L->head; p != NULL; p = p->next) {
    print_set(p->val);
  }
}

ulist* coloring_sub(list* g, unsigned long n, unsigned long X, int l) {
  int k = hash_search(COLOR, X);
  if (k != -1) {
    ulist* hres = ulist_copy(COLOR[k].family);
    return hres;
  }
  
  // X が空集合なら，その分割も空集合
  if (count_bits(X) == 0) {
    return NULL;
  }

  // mis に g[X] の極大部分集合の集合を入れる
  ulist* mis;
  k = hash_search(MIS, X);
  if (k != -1) {
    mis = ulist_copy(MIS[k].family);
  } else {
    mis = (ulist*)calloc(1, sizeof(ulist));
    miss(g, n, X, 0, mis);
    hash_insert(MIS, X, mis);
  }

  // X の分割のサイズは高々 X <= n であるため，
  // それより大きい値 n+1 で最適値 opt_val を初期化
  // 分割のサイズが最小となる最適な分割 OPT も NULL で初期化
  int opt_val = n+1;
  ulist* OPT = NULL;
  for (unode* p = mis->head; p != NULL; p = p->next) {
    // g[X] の極大独立集合 I を X から取り除いた集合 Y = X\I の分割を再帰的に計算
    unsigned long I = p->val;
    unsigned long Y = X;
    // 下の 2 行で Y = X\I を計算
    Y |= I;
    Y -= I;

    // Y = X\I での最適な分割を計算
    ulist* L = coloring_sub(g, n, Y, l+1);
    if (L == NULL) {
      // Y = X \cup I = {} であり，X の最適な分割は { I }
      ulist* C = (ulist*)calloc(1, sizeof(ulist));
      upush(C, X);
      return C;
    }
    if (L->size + 1 < opt_val) {
      // X の分割のサイズ（g[X]の彩色数）が現時点の候補 opt_val よりも小さかったら
      // X の分割 OPT を更新
      opt_val = L->size + 1;
      OPT = L;
      // Y の分割を { Y_1, Y_2, ..., Y_{L->size} } として，
      // X の最適な分割を { Y_1, Y_2, ..., Y_{L->size} } \cup { I } へ
      upush(OPT, I); 
    } else {
      // この L は Y の最適な分割ではないので削除
      uclear(L);
    }
  }

  // g[X] の極大独立集合の集合 mis はもう使わないので削除
  uclear(mis);
  hash_insert(COLOR, X, OPT);
  return OPT;
}

// 各頂点に何色を塗るか（整数を割当てるか）を配列 A で表現
// 配列 A を返す
int* coloring(list* g, int n) {
  unsigned long N = (unsigned long)n; // グラフの頂点数
  unsigned long s = (1ULL << n) - 1;  // 残りの頂点を表す集合，ビット列で集合を表現

  int* A = (int*)malloc(n * sizeof(int));

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

  // 得られた分割に沿って頂点に色を塗る
  /* print_family(S); */
  unsigned color = 1;
  for (unode* p = S->head; p != NULL; p = p->next) {
    unsigned set = p->val;
    for (unsigned i = 0; set > 0; ++i, set = set >> 1) {
      if ((set & 1) == 1) {
	A[i] = color;
      }
    }
    ++color;
  }
  
  uclear(S);
  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);
  list* g = (list*)calloc(n, sizeof(list));

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

  int* A = coloring(g, n);
  for (int i = 0; i < n; ++i) {
    printf("%d ", A[i]);
  }
  putchar('\n');
  
  free(A);

  for (int i = 0; i < n; ++i) {
    clear(&(g[i]));
  }
  free(g);

  hash_clear(MIS);
  hash_clear(COLOR);
  
  return 0;
}