Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | colorare.in, colorare.out | Sursă | Bursele Agora 2006 |
Autor | Cosmin Silvestru Negruseri | Adăugată de | |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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.
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 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.
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.
Restrictii
- 1 ≤ N ≤ 15
- 0 ≤ M ≤ N(N-1)/2
Exemplu
colorare.in | colorare.out |
3 1 1 2 | 2 4 |