Fişierul intrare/ieşire:colorare.in, colorare.outSursăBursele Agora 2006
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.incolorare.out
3 1
1 2
2 4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content