Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-02-29 19:17:34.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:graf2.in, graf2.outSursăInfoarena Monthly 2012, Runda 2
AutorMihai CalanceaAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 le 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 ≤ 100000
  • 1 ≤ M ≤ 200000

Exemplu

graf2.ingraf2.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?