Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-06-18 14:19:43.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:orient.in, orient.outSursăInfoarena Monthly 2012, Runda 6
AutorVlad IonescuAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test1.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Orient

Se da un graf orientat cu N noduri si M muchii.
Prin a reorienta o muchie se intelege ca daca in graf exista muchia (a, b) (adica muchie de la nodul a spre nodul b), muchia se sterge si se plaseaza in locul ei muchia (b, a) (de la nodul b spre nodul a).
De asemenea, prin notiunea de ciclu intr-un graf se intelege o secventa de noduri (v1, v2, ..., vk), cu proprietatea ca pentru orice i ≤ k-1 in graf exista muchie de la nodul vi spre nodul vi+1, si de asemenea exista muchie de la nodul vk spre nodul v1.

Cerinta

Reorientati un numar minim de muchii din graful dat, astfel incat acesta sa contina cel putin un ciclu. Se garanteaza ca exista un numar de muchii (eventual 0) ce pot fi reorientate astfel incat sa se formeze ciclu.

Date de intrare

Fişierul de intrare orient.in contine pe prima linie doua numere naturale N si M, separate prin cate un spatiu, reprezentand numarul de noduri, respectiv numarul de muchii ale grafului. Urmatoarele M linii contin fiecare cate doua numere naturale distincte a si b, separate prin cate un spatiu, cu proprietatea ca in graf exista o muchie orientata de la nodul a spre nodul b.

Date de ieşire

În fişierul de ieşire orient.out se va gasi pe prima linie un singur numar natural, reprezentand numarul minim de muchii care trebuie reorientate pentru a forma un ciclu.

Restricţii

  • 2 ≤ N ≤ 2000
  • 2 ≤ M ≤ 5000
  • Daca graful contine deja un ciclu, raspunsul problemei va fi 0.
  • Un ciclu nu trebuie neaparat sa contina toate cele N noduri ale grafului. Un ciclu poate contine minim 2 noduri.

Exemplu

orient.inorient.out
5 5
1 2
3 2
3 4
4 1
4 5
1

Explicaţie

Putem reorienta muchia (3 2), obtinand astfel ciclul: (1, 2, 3, 4).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?