Fişierul intrare/ieşire:jimmy.in, jimmy.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.15 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Jimmy

Jimmy studiaza la universitate Algoritmi Avansati pe Grafuri. Ultima sa tema consta in gasirea unui cuplaj maxim intr-un tip special de graf. Acest graf este neorientat, are N noduri, iar fiecare nod are gradul 3. Mai mult, graful este biconex din punct de vedere al muchiilor (adica trebuie eliminate cel putin 2 muchii pentru ca graful sa nu mai fie conex). Un cuplaj este o submultime a muchiilor grafului, astfel incat oricare 2 muchii din submultime nu au nici un capat comun. Un cuplaj maxim este un cuplaj avand cardinal maximal.
Fiind date o serie de grafuri speciale avand proprietatile precizate mai sus, gasiti cardinalul unui cuplaj maxim pentru fiecare graf.

Date de intrare

Prima linie a fisierului de intrare jimmy.in contine numarul intreg T, reprezentand numarul de grafuri descrise in continuare. Descrierea fiecarui graf contine pe prima linie numarul intreg par N, reprezentand numarul de noduri ale grafului. Fiecare din urmatoarele 3*N/2 linii contine cate 2 numere intregi, A si B, separate printr-un spatiu, avand semnificatia ca exista o muchie intre nodul A si nodul B. Nodurile sunt numerotate de la 1 la N.

Date de iesire

Pentru fiecare din cele T grafuri date in fisierul de intrare, afisati in fisierul de iesire jimmy.out cate o linie continand cardinalul unui cuplaj maxim.

Restrictii

  • 1 ≤ T ≤ 50
  • 4 ≤ N ≤ 5000

Exemplu

jimmy.injimmy.out
2
4
1 2
1 3
1 4
2 3
2 4
3 4
4
1 2
1 3
1 4
2 3
2 4
3 4
2
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content