Fişierul intrare/ieşire:connect.in, connect.outSursăShumen 2019 Juniori
AutorMartin KopchevAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test2.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inconnect.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?