Cod sursă (job #811892)

#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream in("zapada.in");
ofstream out("zapada.out");
int n, m, k;
pair<int, pair<int, int>> v[100005];
vector<int> vec[10005];
int tata[10005];
int dim[10005];

int rad(int x)
{
    if(x == tata[x])
    {
        return x;
    }

    int r = rad(tata[x]);
    tata[x] = r;
    return r;
}

void unire(int x, int y)
{
    int rx = rad(x);
    int ry = rad(y);

    if(rx == ry)
    {
        return;
    }

    if(dim[ry] > dim[rx])
    {
        swap(rx, ry);
    }

    tata[ry] = rx;
    dim[rx] += dim[ry];
}

int check(int x, int y)
{
    return (rad(x) == rad(y));
}

int main()
{
    in>>n>>m>>k;

    int x, y, z;
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y>>z;

        v[i] = {z, {x, y}};
    }

    for(int i = 1; i<=n; i++)
    {
        tata[i] = i;
        dim[i] = 1;
    }

    sort(v + 1, v + m + 1);

    int cnt = n - 1;
    int ans = 0;
    for(int i = 1; i<=m; i++)
    {
        if(cnt == 0)
        {
            break;
        }

        pair<int, pair<int, int>> it = v[i];

        if(check(it.second.first, it.second.second) == 0)
        {
            unire(it.second.first, it.second.second);
            ans += it.first;
            cnt--;

            vec[it.second.first].push_back(it.second.second);
            vec[it.second.second].push_back(it.second.first);
        }
    }

    out<<ans<<'\n';

    return 0;
}