Un tgraf este un graf neorientat avand una dintre urmatoarele proprietati:
are un singur varf
contine un varf izolat (care nu este adiacent cu nici un alt varf), iar graful obtinut prin inlaturarea
acestui varf este un tgraf
contine un varf care este adiacent cu toate celelalte, iar graful obtinut prin inlaturarea acestui varf
si a muchiilor adiacente este un tgraf
O definitie echivalenta a unui tgraf este urmatoarea: fiecarui nod K
i se poate atribui o valoare nenegativa a[K],
astfel incat sa existe un numar intreg strict pozitiv T,
cu proprietatea ca orice submultime de varfuri din graf este independenta
daca si numai daca suma valorilor asociate varfurilor din submultime este strict
mai mica decat T. O submultime se numeste independenta
daca este adevarata una din urmatoarele afirmatii:
este formata dintr-un singur varf
intre oricare doua varfuri care fac parte din submultime nu exista muchie
Cerinta
Dandu-se un tgraf, atribuiti fiecarui nod K o valoare nenegativa a[K] si determinati numarul T,
astfel incat sa fie respectata definitia precizata mai sus.
Date de intrare
Pe prima linie a fisierului tgraf.in se afla un numar intreg
P, reprezentand numarul de tgrafuri ce vor fi descrise in continuare. Un tgraf este descris pe
mai multe linii, astfel:
pe prima linie se afla numerele intregi N si
M, separate printr-un spatiu, reprezentand numarul de varfuri si numarul de muchii ale tgrafului
pe urmatoarele M linii se afla cate doua numere intregi distincte a si b,
din multimea {1,2,..,N},
avand semnificatia ca exista muchie intre varful numerotat cu a
si cel numerotat cu b
Descrierile a doua tgrafuri consecutive sunt separate printr-o linie
goala.
Date de iesire
Pentru fiecare dintre cele P tgrafuri din fisierul de intrare va trebui
sa afisati cate doua linii in fisierul tgraf.out:
prima linie va contine numarul T, iar a doua va contine N
numere intregi nenegative, reprezentand valorile asociate varfurilor, in ordine,
de la 1 la N.
Restrictii si precizari
1 <= P <= 20
1 <= N <= 25
0 <= M <= N*(N-1)/2
Numarul determinat T
si valorile asociate varfurilor trebuie sa fie mai mici sau egale cu 109
In general, solutia nu este unica.
Exemplu
tgraf.in
tgraf.out
4
1 0
2 0
3 3
1 2
1 3
2 3
4 2
1 4
3 4
1
0
1000
10 20
2
1 1 1
8
2 1 4 6
Mugurel Ionut Andreica
student Universitatea "Politehnica" Bucuresti
Contact: mugurel_ionut at yahoo.com