| Fişierul intrare/ieşire: | conexidad.in, conexidad.out | Sursă | OJI 2019, clasele 11-12 |
| Autor | Mihai Calancea | Adăugată de |  Baltatu Andrei-Mircea •Archazey |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Conexidad
Fie un graf neorientat cu N noduri şi M muchii, care NU este conex.
Cerinţă
Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex.
Fie extrai numărul de muchii nou-adăugate care sunt incidente cu nodul i, iar max_extra cea mai mare dintre valorile extra1 , extra2 ,... , extraN . Mulţimea de muchii adăugate trebuie să respecte condiţia ca valoarea max_extra să fie minimă.
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.
Date de ieşire
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].
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.
Exemple
| 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 extra1 = 1, extra2 = 0, extra3 = 1, extra4 = 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 extra1 = 1, extra2 = 1, extra3 = 2, extra4 = 1, extra5 = 1, deci max_extra = 2. Se poate demonstra că nu există soluţie cu max_extra < 2. |
