Stefan Dascalescu stefdasca.ro (stefdasca) Cerința
Gigel are un graf cu n noduri și m muchii, care nu este conex. El dorește să afle răspunsul la două întrebări:
1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex?
2) Dacă costul adăugării unei muchii între nodurile a și b este a + b, care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?
Date de intrare
Fișierul de intrare unire.in conține pe prima linie numerele n și m, pe a doua linie conține numărul c, reprezentând numărul cerinței 1 ≤ c ≤ 2, iar pe următoarele m linii se află muchiile grafului a b, 1 ≤ a, b ≤ n, a ≠ b.
Date de ieșire
Fișierul de ieșire unire.out va conține pe prima linie numărul S, reprezentând răspunsul cerut de Gigel.
Restricții și precizări
1 ≤ n ≤ 100000,0 ≤ m < n-1- Pentru teste în valoare de
30de puncte, cerința va fi1. - Pentru teste în valoare de
40de puncte,1 ≤ n ≤ 1000.
Exemple:
unire.in
6 3 1 1 2 3 4 5 6
unire.out
2
unire.in
6 3 2 1 2 3 4 5 6
unire.out
10
Explicație
Se vor uni nodurile 1 și 3, respectiv nodurile 1 și 5, s-au folosit 2 muchii, iar costul total va fi 1 + 3 + 1 + 5 = 10.