Revizia anterioară Revizia următoare
| 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
Note: This is the translated version of the statement. For the English (original) version of the statement, click here.
Cerinţă
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 indexate 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 2 numere: u si v, care denota faptul ca exista o muchie 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 ≤ 2000, m ≤ 5000
- Pentru alte 40 de puncte, n ≤ 200
- 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).
