== include(page="template/taskheader" task_id="connect") ==
Poveste şi 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 numerotate intre $i$ si $j$ inclusiv.
Sa se afle cate dintre aceste grafuri sunt conexe.
h2. Date de intrare
Fişierul de intrare $connect.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $connect.out$ ...
În fişierul de ieşire $connect.out$ se va afisa pe o singura linie numarul de grafuri conectate gasite.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ n ≤ 50.000$
* $1 ≤ m ≤ 200.000$
* $1 ≤ u, v ≤ n$
* Graful poate contine mai multe muchii intre aceleasi 2 noduri.
h2. 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.
h2. Exemplu
table(example). |_. connect.in |_. connect.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 4 4
1 2
2 4
1 3
1 4
| 3 |
h3. Explicaţie
...
Perechile $(i, j)$, pentru care graful rezultant este conectat, sunt $(1, 3)$, $(1, 4)$ si $(2, 4)$.
== include(page="template/taskfooter" task_id="connect") ==
