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 memorie16384 kbytes
Scorul tăuN/ADificultateN/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.ingraf2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content