== include(page="template/taskheader" task_id="conexidad") ==
Poveste şi cerinţă...
Fie un graf neorientat cu $N$ noduri şi $M$ muchii, care **NU este conex**.
h2. Date de intrare
Fişierul de intrare $conexidad.in$ ...
h2. Cerinţă
h2. Date de ieşire
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ă.
În fişierul de ieşire $conexidad.out$ ...
h2. Restricţii
h2. Date de intrare
* $... ≤ ... ≤ ...$
Pe prima linie a fişierului de intrare $conexidad.in$ se află două numere naturale $N$ şi $M$, iar pe fiecare dintre următoarele $M$ linii se află câte o pereche de numere $a, b$, semnificând faptul că există muchia $[a,b]$. Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.
h2. Exemplu
h2. Date de ieşire
table(example). |_. conexidad.in |_. conexidad.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
Fişierul de ieşire $conexidad.out$ va conţine pe prima linie valoarea $max_extra$. Pe a doua linie va conţine valoarea $K$ reprezentând numărul de muchii nou-adăugate în graf. Fiecare dintre următoarele $K$ linii va conţine câte o pereche de numere $c, d$, separate prin câte un spaţiu, semnificând faptul că se adaugă grafului muchia $[c,d]$.
h3. Explicaţie
h2. Restricţii şi precizări
...
* $1 ≤ N ≤ 100$
* $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$ 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.
h2. Exemple
table(example).
|_. conexidad.in
|_. conexidad.out
|_. Explicatii si comentarii
|
| 4 2
1 2
4 2
| 1
1
3 1
| Graful este format din două componente conexe, cu noduri din
mulţimea {1,2,4} respectiv nodul izolat 3.
După adăugarea muchiei (3,1) vom avea valorile $extra{~1~}$ = 1,
$extra{~2~}$ = 0, $extra{~3~}$ = 1, $extra{~4~}$ = 0, deci max_extra = 1.
Se poate demonstra că nu există soluţie cu max_extra < 1.
|
| 5 1
3 4
| 2
3
1 3
2 3
4 5
| Graful este format din patru componente conexe, cu noduri din
mulţimea {3,4}, respectiv nodurile izolate 1, 2 şi 5.
După adăugarea muchiilor (1,3), (2,3) şi (4,5), vom avea
valorile $extra{~1~}$ = 1, $extra{~2~}$ = 1, $extra{~3~}$ = 2, $extra{~4~}$ = 1,
$extra{~5~}$ = 1, deci max_extra = 2.
Se poate demonstra că nu există soluţie cu max_extra < 2.
|
== include(page="template/taskfooter" task_id="conexidad") ==
== include(page="template/taskfooter" task_id="conexidad") ==
