| Fişierul intrare/ieşire: | graf2.in, graf2.out | Sursă | Infoarena Monthly 2012, Runda 2 |
| Autor | Mihai Calancea | Adăugată de |  Mr. Noname •cezar305 |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Graf2
Se da un graf orientat A=(V, E) si se zice ca exista drum de la X la Y (X, Y apartin lui V) daca pornind de la X si mergand pe arcele grafului se poate ajunge in Y. Sa se gaseasca numarul minim de arce ale unui graf B=(V,E2) cu proprietatea ca exista un drum de la X la Y in graful B daca si numai daca exista un drum de la X la Y in graful A.
Date de intrare
Fişierul de intrare graf2.in se afla pe prima linie doua numere intregi N si M reprezentand numarul de noduri si respectiv numarul de arce ale grafului A. Pe urmatoarele M linii se vor afla cate doi intregi X si Y reprezentand faptul ca in graful A exista arc de la X inspre Y.
Date de ieşire
În fişierul de ieşire graf2.out se va afla un singur numar reprezentand numarul minim de arce ale grafului B.
Restricţii
- 1 ≤ N ≤ 600
- 1 ≤ M ≤ 10.000
Exemplu
| graf2.in | graf2.out |
|---|---|
| 3 3 1 2 2 3 1 3 | 2 |
Explicaţie
Se poate crea graful B cu arcele 1->2 si 2->3, respectandu-se proprietatea grafului.
