colorare

Colorare

== include(page="template/taskheader" task_id="colorare") ==

==Include(page="template/taskheader" task_id="colorare")==

Poveste ...

Se considera un graf cu $N$ noduri si $M$ muchii. Numim o colorare valida a nodurilor grafului, o colorare in care oricare doua noduri vecine sunt colorate distinct.

h2. Cerinta

...

Se cere determinarea numarului minim de culori necesar pentru o colorare valida. Pentru acest numar minim de culori se cere numarul de colorari valide ale nodurilor grafului.

h2. Restrictii

h2. Date de intare

...

In fisierul de intrare $colorare.in$ vom avea pe prima linie doua numere intregi $N$ si $M$. Pe urmatoarele $M$ linii se vor afla cate doua numere intregi, separate intre ele printr-un spatiu, $X$ si $Y$, cu semnificatia ca exista o muchie in graf intre nodurile $X$ si $Y$.

h2. Date de intrare

h2. Date de iesire

...

Fisierul de iesire $colorare.out$ va contine pe prima linie o pereche de intregi $p$ si $c$, care reprezinta numarul minim de culori cu care pot fi colorate nodurile grafului respectand conditia din problema, respectiv numarul de colorari posibile ale grafului cu $p$ culori distincte.

h2. Date de iesire

h2. Restrictii

...

* $1 ≤ N ≤ 15$
* $0 ≤ M ≤ N(N-1)/2$

h2. Exemplu

| colorare.in | colorare.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. colorare.in |_. colorare.out |
| 3 1
1 2
| 2 4 |
 
==Include(page="template/taskfooter" task_id="colorare")==
 

== include(page="template/taskfooter" task_id="colorare") ==

993