// Graph färben
//
// Aufruf: colors
//
// Klaus Kusche, 2011

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

#define STAEDTE 6

int verbind[STAEDTE][STAEDTE] = {
  { 0, 0, 1, 1, 0, 1 },
  { 0, 0, 1, 0, 0, 0 },
  { 1, 1, 0, 1, 0, 0 },
  { 1, 0, 1, 0, 1, 1 },
  { 0, 0, 0, 1, 0, 1 },
  { 1, 0, 0, 1, 1, 0 }
};

int farben[STAEDTE];
int maxfarben;

void drucke(void)
{
  int s;
  printf("%d Farben: ", maxfarben);
  for (s = 0; s < STAEDTE; ++s)
    printf("%d ", farben[s]);
  putchar('\n');
  exit(0);
}

int ok(int farbe, int stadt)
{
  int s;
  for (s = 0; s < stadt; ++s) {
    if (verbind[stadt][s] && (farben[s] == farbe))
      return 0;
  }
  return 1;
}

void probier(int stadt)
{
  int farbe;
  for (farbe = 0; farbe < maxfarben; ++farbe) {
    if (ok(farbe, stadt)) {
      farben[stadt] = farbe;
      if (stadt == STAEDTE - 1)
        drucke();
      else
        probier(stadt + 1);
    }
  }
}

int main(void)
{
  farben[0] = 0;
  for (maxfarben = 2; ; ++maxfarben) {
    probier(1);
  }
}