| Fişierul intrare/ieşire: | grarb.in, grarb.out | Sursă | FMI No Stress 2010 |
| Autor | Marius Dumitran, Vlad Duta | Adăugată de |  Dumitran Adrian Marius •marius135 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Grarb
Se da un graf G neorientat cu N noduri numerotate de la 1 la N si M muchii. Determinati numarul minim de muchii care trebuie eliminate si numarul minim de muchii care trebuie adaugate in graful G astfel incat acesta sa devina arbore.
Date de intrare
Fişierul de intrare grarb.in contine pe prima linie doua numere naturale N si M reprezentand numarul de noduri respectiv numarul de muchii ale lui G. Pe fiecare din urmatoarele M linii se afla cate doua numere naturale x si y cu semnificatia ca exista o muchie intre nodurile x si y. Intre doua noduri pot exista mai multe muchii si pot exista muchii de la un nod la el insusi.
Date de ieşire
În fişierul de ieşire grarb.out se va afisa pe prima linie numarul minim de muchii ce trebuiesc eliminate, iar pe cea de-a doua linie numarul minim de muchii care trebuie adaugate pentru ca graful G sa fie transformat in arbore.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 200 000
Exemplu
| grarb.in | grarb.out |
|---|---|
| 6 5 1 2 1 3 2 4 1 4 5 6 | 1 1 |
Explicatii
O solutie posibila este sa se elimine muchia (1,4) si sa se adauge muchia (2,5)
