Colorare

colorare

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

== include(page="template/taskheader" task_id="colorare") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| colorare.in | colorare.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="colorare") ==

==Include(page="template/raw")==
 
Colorare
 
 
 
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.
 
 
 
Date de intare
 
In fisierul de intrare gcolor.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 Iesire
 
Fisierul de iesire gcolor.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.
 
 
 
Restrictie
 
1 <= N <= 15;
0 <= M <= N(N-1)/2.
 
h2. Exemplu
 
 
|gcolor.in |gcolor.out |
 
|3 1 |2 4 |
|1 2 | |
 
 
 
==Include(page="template/taskfooter" task_id="colorare")==