| Fişierul intrare/ieşire: | drum4.in, drum4.out | Sursă | FMI No Stress 3 |
| Autor | Ionut Bogdanescu | Adăugată de |  Ionut Bogdanescu •swift90 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | drum4.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.
