POJ 1129 Channel Allocation

問題

頂点と辺の情報が与えられる。最小で何色で頂点を塗ることができるか答えよ。

やりかた

四色定理から必ず4以下になる。
色を数値で管理して、深さ優先探索でグラフを探索する。探索中に次に訪れる点に隣接している点の色で使っていない色のうち、最も値の小さい色を次に訪れる点の色にすればいい。すべての点で探索が終わったら使った色の数を数える。

以下ソース。

int color[30];
bool adj[30][30];
int n;

int ret(int idx){
  bool used[4] = {false};
  for(int i = 0; i < n; i++)
    if(adj[idx][i] && color[i] != -1)
      used[color[i]] = true;
  for(int i = 0; i < 4; i++)
    if(!used[i]) return i;
}
void dfs(int i){
  for(int j = 0; j < n; j++){
    if(!adj[i][j] || color[j] != -1) continue;
    color[j] = ret(j);
    dfs(j);
  }
  return;
}

int main(int argc, char **argv){
  while(scanf("%d", &n), n){
    FILL(color, -1);
    FILL(adj, false);
    for(int k = 0; k <n; k++){
      char s[30]; scanf("%s", s);    
      for(int i = 2; i < strlen(s); i++)
	adj[s[0] - 'A'][s[i] - 'A'] = true;
    }

    for(int i = 0; i < n; i++){
      if(color[i] != -1) continue;
      color[i] = 0;
      dfs(i);
    }

    set<int> r(color, color + n);
    if(r.size() == 1)
      printf("%d channel needed.\n", r.size());
    else
      printf("%d channels needed.\n", r.size());
  }
  return 0;
}