Minimum spanning tree (Kruskal)

kruskal.cpp

// https://cses.fi/problemset/task/1675/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class DSU {
   private:
    vector<ll> v;

   public:
    DSU(ll N) {
        v = vector<ll>(N, -1);
    }

    ll get(ll x) {
        if (v[x] < 0) {
            return x;
        }
        return v[x] = get(v[x]);
    }

    bool same_set(ll a, ll b) {
        return get(a) == get(b);
    }

    bool unite(ll a, ll b) {
        ll x = get(a), y = get(b);

        if (x == y) {
            return false;
        }

        if (v[x] > v[y]) {
            swap(x, y);
        }

        v[x] += v[y];
        v[y] = x;

        return true;
    }

    ll size(ll x) {
        return -v[get(x)];
    }
};

ll MST(vector<pair<ll, pair<ll, ll>>> &edges, ll n) {
    sort(edges.begin(), edges.end());

    DSU dsu(n + 1);
    ll ans = 0;

    for (auto [cost, edge] : edges) {
        if (!dsu.same_set(edge.first, edge.second)) {
            ans += cost;
        }
        dsu.unite(edge.first, edge.second);
    }

    return dsu.size(1) == n ? ans : -1;
}

int main() {
    ll n, m;
    cin >> n >> m;

    vector<pair<ll, pair<ll, ll>>> v;

    while (m--) {
        ll a, b, c;
        cin >> a >> b >> c;

        v.push_back({c, {a, b}});
    }

    ll ans = MST(v, n);

    if (ans >= 0) {
        cout << ans;
    } else {
        cout << "IMPOSSIBLE";
    }
}