Rezolvare PBinfo #2968

Fie un graf neorientat cu N noduri și M muchii, care NU este conex.

Cerința

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 ≠ 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.
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:

conexidad.in

4 2
1 2
4 2

conexidad.out

1
1
3 1

Explicație

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.

Exemplul 2:

conexidad.in

5 1
3 4

conexidad.out

2
3
1 3
2 3
4 5

Explicație

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.