Problem conexidad


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

Cerinţe

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

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.
  • Se acordă 10 puncte din oficiu.

Exemple

conexidad.in

4 2
1 2
4 2

conexidad.out

1
1
3 1

conexidad.in

5 1
3 4

conexidad.out

2
3
1 3
2 3
4 5

Explicații

Pentru primul test:
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.
Pentru al doilea test:
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.

General info

ID: 20

Upload: liviu

Input: conexidad.in/conexidad.out

Memory limit: 64MB/32MB

Time limit: 0.05s

Author: Mihai Calancea

Source: OJI 2019 XI-XII: Problema 1

Points by default: 10p

Submissions

Special Submissions