Fişierul intrare/ieşire:conexidad.in, conexidad.outSursăOJI 2019, clasele 11-12
AutorMihai CalanceaAdăugată deArchazeyBaltatu Andrei-Mircea Archazey
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?