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?

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 30 de puncte, cerința va fi 1.
• Pentru teste în valoare de 40 de 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.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("unire.in");
ofstream cout("unire.out");

vector <int> G[100001];
int n , C[100001] , nc , cer , m , f[100001];
long long s;

void dfs(int v , int c)
{
    C[v] = c;
    for(int i :G[v])
        if(!C[i]) dfs(i , c);
}

int main()
{
    cin >> n >> m >> cer;
    int x , y;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; i++)
        if(!C[i])
        {
            nc++;
            dfs(i , i);
        }
    if(cer == 1) cout << nc - 1;
    else
    {
        sort(C + 1 , C + n + 1);
        for(int i = 2 ; i <= n ; i++)
        {
            if(C[1] != C[i] && f[C[i]] == 0) s += (C[1] + C[i]);
            f[C[i]]++;
        }
        cout << s;
    }
}