Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | orient.in, orient.out | Sursă | Infoarena Monthly 2012, Runda 6 |
| Autor | Vlad Ionescu | Adăugată de |  Mr. Noname •cezar305 |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | orient.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).
