Coloració de grafs P14514

Donat un graf no dirigit, una coloració d’aquest graf és una assignació de colors a cadascun dels vèrtexs del graf de forma que cap aresta tingui extrems del mateix color. El nombre cromàtic d’un graf és el mínim nombre de colors necesaris per colorar un graf donat.

Com que trobar el nombre cromàtic d’un graf és computacionalment molt costós, en aquest problema usarem un algorisme golafre que sol trobar una coloració prou bona:

Considerant que els vèrtexs i els colors venen identificats per nombres de zero a n−1, l’algorisme golafre agafa els vèrtexs seqüencialment (per ordre d’identificador) i els coloreja amb el color més baix possible amb el qual no s’hagi colorejat ja algun dels seus veïns.

Per exemple, el nombre de colors emprats per l’algorisme golafre al graf següent és XXX.

DIBUIX

Entrada

L’entrada conté diferents grafs (potser cap). Cadascun comença amb n i m, corresponent al nombre de vèrtexs i arestes del graf. Segueixen m parells u,v, indicant que hi ha una aresta entre u i v. Es té que n>0, que 0≤ u < v <n i que no hi ha arestes repetides. Suposeu que els grafs no són densos.

Sortida

Per a cada graf, escriviu el nombre de colors emprats per l’algorisme golafre.