| Fişierul intrare/ieşire: | connect.in, connect.out | Sursă | Shumen 2019 Juniori |
| Autor | Martin Kopchev | Adăugată de |  Matteo Verzotti •Matteoalexandru |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Connect
Se da un graf neorientat cu n noduri si m muchii. Muchiile sunt numerotate in ordinea in care sunt date in fisierul de intrare.
Pentru fiecare pereche (i, j) pentru care 1 ≤ i ≤ j ≤ m, se creeaza cate un graf cu n noduri si muchiile initiale numerotate intre i si j inclusiv.
Sa se afle cate dintre aceste grafuri sunt conexe.
Date de intrare
Fişierul de intrare connect.in contine pe prima linie numerele n si m. Pe fiecare din urmatoarele m linii se afla cate 2 numere: u si v, care denota faptul ca exista o muchie bidirectionala intre u si v.
Date de ieşire
În fişierul de ieşire connect.out se va afisa pe o singura linie numarul de grafuri conectate gasite.
Restricţii
- 2 ≤ n ≤ 50.000
- 1 ≤ m ≤ 200.000
- 1 ≤ u, v ≤ n
- Graful poate contine mai multe muchii intre aceleasi 2 noduri.
Punctare
- Pentru 5 puncte, n ≤ 100, m ≤ 200
- Pentru alte 15 puncte, n ≤ 2.000, m ≤ 5.000
- Pentru alte 40 de puncte, n ≤ 200, m ≤ 200.000
- Pentru restul de 40 de puncte se aplica restrictiile initiale.
Exemplu
| connect.in | connect.out |
|---|---|
| 4 4 1 2 2 4 1 3 1 4 | 3 |
Explicaţie
Perechile (i, j), pentru care graful rezultant este conectat, sunt (1, 3), (1, 4) si (2, 4).
