Revizia anterioară Revizia următoare
| 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
Anca, vazand ca ONI 2012 se apropie cu pasi repezi, s-a hotarat s-o ajute pe sora ei mai mica (Gabi) sa se pregateasca. Dar, dupa ce i-a aratat cativa algoritmi pe grafuri, a vazut ca aceasta ii cunostea si ca incepuse sa se plictiseasca. Asa ca s-a gandit sa ii arate o problema pe care o invatase de la ultimul ei profesor. Problema suna asa:
"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 muchiile grafului se poate ajunge in Y.
Sa se gaseasca numarul minim de muchii ale unui graf B=(V,E2) cu proprietatea ca daca exista drum de la X la Y in graful A, atunci exista drum de la X la Y si in graful B."
Saraca Anca! Intr-un moment a uitat rezolvarea problemei. Acum ea va roaga sa o ajutati sa-si reaminteasca rezolvarea si in schimb va promite 100 de puncte si tot norocul in fazele urmatoare ale concursului.
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 muchii ale grafului A. Pe urmatoarele M linii se vor afla cate doi intregi X si Y reprezentand faptul ca in graful A exista muchie 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 muchii ale grafului B.
Restricţii
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 30.000
Exemplu
| graf2.in | graf2.out |
|---|---|
| 3 3 1 2 2 3 1 3 | 2 |
Explicaţie
Se poate crea graful B cu muchiile 1->2 si 2->3 , respectandu-se proprietatea grafului
