#include <algorithm>
#include <numeric>
#include <vector>

int find(std::vector<int>& parent, int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

int kruskal(int n, std::vector<std::vector<int>> edges) {
    std::vector<int> parent(n);
    std::iota(parent.begin(), parent.end(), 0);
    std::sort(edges.begin(), edges.end(), [](const auto& x, const auto& y) {
        if (x[2] != y[2]) return x[2] < y[2];
        int lx = std::min(x[0], x[1]), ly = std::min(y[0], y[1]);
        if (lx != ly) return lx < ly;
        return std::max(x[0], x[1]) < std::max(y[0], y[1]);
    });
    int total = 0;
    int used = 0;
    for (const auto& e : edges) {
        int a = e[0], b = e[1], w = e[2];
        int ra = find(parent, a);
        int rb = find(parent, b);
        if (ra == rb) continue;
        parent[rb] = ra;
        total += w;
        used++;
        if (used == n - 1) break;
    }
    return total;
}
More from Graphs
