grarb

Grarb

== include(page="template/taskheader" task_id="grarb") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $grarb.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $grarb.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 200 000$

h2. Exemplu
table(example). |_. grarb.in |_. grarb.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 5
  1 2
  1 3
  2 4
  1 4
  5 6
| 1
  1

|

h3. Explicaţie

h3. Explicatii

...

!problema/grarb?img.jpg 50%!
 
O solutie posibila este sa se elimine muchia (1,4) si sa se adauge muchia (2,5)

== include(page="template/taskfooter" task_id="grarb") ==

5133