Colorare

colorare

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

== include(page="template/taskheader" task_id="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.

Poveste ...

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. Date de intare

h2. Restrictii

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 iesire

h2. Date de intrare

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. Restrictii

h2. Date de iesire

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

...

h2. Exemplu

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

| colorare.in | colorare.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="colorare") ==

993