Алгоритм Краскала

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <stdio.h>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <iterator>
#include <map>
#include <iomanip>
#include <unordered_set>
#include <array>
#define int long long
#define pb push_back
#define fir first
#define sec second
#define double long double
#define endl "\n"
#define un unsigned
#define INF 1000000000009
#define EPS 0.000000000001
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;

vector <int> p(100005);

int rk[100005];

void make_set(int v)
{
    p[v] = v;
    rk[v] = 0;
}

int dsu_get(int v)
{
    if (v == p[v])
    {
        return v;
    }

    return p[v] = dsu_get(p[v]);
}

void union_set(int a, int b)
{
    a = dsu_get(a);
    b = dsu_get(b);

    if (a == b)
    {
        return;
    }

    if (rk[a] > rk[b])
    {
        swap(a, b);
    }

    if (rk[a] == rk[b])
    {
        rk[b]++;
    }

    p[a] = b;

    return;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, q;
    cin >> n >> m;

    vector <pair <int, pii>> gr;

    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;

        gr.pb({ w, { a, b } });
    }

    int cost = 0;

    vector<pii> res;

    sort(all(gr));

    for (int i = 0; i < n; i++)
    {
        make_set(i);
    }

    for (int i = 0; i < m; i++)
    {
        int a = gr[i].second.first;
        int b = gr[i].second.second;
        int l = gr[i].first;

        if (dsu_get(a) != dsu_get(b))
        {
            cost += l;
            res.push_back(gr[i].second);
            union_set(a, b);
        }
    }

    if (res.size() == n - 1)
    {
        cout << cost;
    }
    else
    {
        cout << "NON-CONNECTED";
    }

    return 0;
}