Fişierul intrare/ieşire:colorare2.in, colorare2.outSursăAlgoritmus, runda 4
AutorCosmin Silvestru NegruseriAdăugată decyberClaudia Cardei cyber
Timp execuţie pe test0.1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Colorare2

Vom considera un graf bipartit. Un graf este bipartit daca exista doua multimi, A si B, astfel incat toate muchiile au un varf in multimea A si unul in multimea B. Se cere sa se coloreze muchiile grafului cu numar minim de culori astfel incat oricare doua muchii care au un varf comun sa fie colorate diferit.

Date de intrare

Pe prima linie a fisierului de intrare colorare2.in se afla trei valori N, M si K reprezentand numarul de varfuri din multimea A, numarul de varfuri din multimea B si numarul de muchii ale grafului. Varfurile din multimea A vor fi etichetate cu valori intre 1 si N. Varfurile din multimea B vor fi etichetate cu valori intre N + 1 si N + M. Pe urmatoarele K linii se afla cate doua valori intregi reprezentand nodurile ce determina muchiile.

Date de iesire

Pe prima linie a fisierului de iesire colorare2.out se va afla numarul de culori folosit. Acest numar il vom nota cu C. Pe fiecare din urmatoarele K linii se va afla cate un numar intreg din intervalul [1, C], reprezentand culorile muchiilor, in ordinea in care acestea apar in fisierul de intrare. In cazul in care exista mai multe solutii corecte, se poate afisa oricare dintre ele.

Restrictii

  • 1 ≤ N, M ≤ 100
  • 1 ≤ K ≤ 2 500

Exemplu

colorare2.incolorare2.out
6 6 10
1 7
1 8
2 8
2 10
3 8
3 9
3 11
4 12
5 9
6 11
3
3
2
1
3
3
1
2
1
3
3

Explicatie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content