conexidad

Conexidad

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

Fie un graf neorientat cu $N$ noduri şi $M$ muchii, care NU este conex.
Să $i$ se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex.
Fie $extra{~i~}$ numărul de muchii nou-adăugate care sunt incidente cu nodul $i$, iar max_extra cea mai mare dintre valorile $extra{~1~}$ , $extra{~2~}$ ,... , $extra{~$~}$N$ . Mulţimea de muchii adăugate trebuie să respecte condiţia ca valoarea $max_extra$ să fie minimă.

Fie un graf neorientat cu $N$ noduri şi $M$ muchii, care **NU este conex**.
 
h2. Cerinţă
 
Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex.
Fie $extra{~i~}$ numărul de muchii nou-adăugate care sunt incidente cu nodul $i$, iar $max_extra$ cea mai mare dintre valorile $extra{~1~}$ , $extra{~2~}$ ,... , $extra{~N~}$ . Mulţimea de muchii adăugate trebuie să respecte condiţia ca valoarea $max_extra$ să fie minimă.

h2. Date de intrare

* $0 ≤ M ≤ N*(N-1)/2$
* Nodurile grafului sunt numerotate de la $1$ la $N$ inclusiv.
* Muchiile prezente în fişierul de intrare sunt distincte.

* Pentru orice muchie $[a,b]$ aflată în fişierul de intrare, avem $a &neq; b$.

* Pentru orice muchie $[a,b]$ aflată în fişierul de intrare, avem $a$ este diferit de $b$.

* Graful din fişierul de intrare nu este conex.
* În cazul în care soluţia afişată pentru un anumit test conectează graful cu număr minim de muchii, dar nu minimizează valoarea lui $max_extra$, se vor acorda $50%$ din punctajul pentru testul respectiv.
* Dacă există mai multe soluţii optime, se va admite oricare dintre acestea.