Fişierul intrare/ieşire:drum4.in, drum4.outSursăFMI No Stress 3
AutorIonut BogdanescuAdăugată deswift90Ionut Bogdanescu swift90
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Drum4

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.
Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

In tara X avem N orase si M drumuri unidirectionale. Cum aceasta tara este foarte tanara, nu se stie daca se poate ajunge din orice oras in orice alt oras al tarii. Pentru a rezolva aceasta dilema este nevoie de ajutorul vostru. Daca nu se poate ajunge din orice oras in orice alt oras, vi se cere numarul minim de drumuri ce trebuie construite pentru a face posibil acest lucru.

Date de intrare

Fişierul de intrare drum4.in contine pe prima linie 2 numere N si M, numarul de orase, respectiv numarul de drumuri. Pe urmatoarele M linii se gasesc 2 numere x si y reprezentand un drum de la orasul x la orasul y.

Date de ieşire

În fişierul de ieşire drum4.out se va afisa numarul minim de drumuri ce trebuie construite astfel incat sa putem ajunge din orice oras in orice alt oras.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 200.000
  • 1 ≤ x,y ≤ N

Exemplu

drum4.indrum4.out
4 3
1 2
2 1
1 3
2

Explicaţie

Se leaga orasul 4 de orasul 1 si orasul 3 de orasul 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?