uniolympiads Ελληνικά

Minimum spanning tree (Kruskal)

Sort the edges by weight and keep those that join two different components. O(mlog⁡m)O(m \log m), with a DSU.

When

You want to connect all vertices at minimum total cost. Or, more often in contests, you want a property of the MST: "what is the maximum weight you must cross to get from aa to bb, at best?" The answer is the heaviest edge on the MST path.

The idea

Cut property: for every partition of the vertices into two parts, the lightest edge joining them belongs to some MST. Kruskal applies it greedily. It goes through the edges from the lightest. When an edge joins two components, it is the lightest edge crossing the cut "this component / everything else", so we keep it. If its endpoints are already in the same component, it would close a cycle, so we drop it.

The code needs the DSU. If the graph is disconnected, it returns the weight of a minimum spanning forest. To know whether a tree exists, count the edges you kept: there must be n−1n - 1.

Pitfalls

  • In Road Reparation the answer is IMPOSSIBLE when the graph is disconnected. That is the "count the edges" above.
  • Weights add up in long long: 2⋅1052 \cdot 10^5 edges times 10910^9.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/kruskal.cpp
// Minimum spanning tree (forest), Kruskal. O(m log m) for the sort.
// Needs dsu.cpp. Edges in increasing weight; keep an edge when it joins two components.
// Returns the total weight; if the graph is disconnected, it is the weight of a minimum spanning forest.

struct WeightedEdge {
    int u;
    int v;
    ll w;
};

ll kruskal(int n, vector<WeightedEdge> edges, vector<WeightedEdge>* chosen = nullptr) {
    sort(edges.begin(), edges.end(), [](const WeightedEdge& a, const WeightedEdge& b) {
        return a.w < b.w;
    });
    DSU dsu(n);
    ll total = 0;
    for (const WeightedEdge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            if (chosen != nullptr) {
                chosen->push_back(e);
            }
        }
    }
    return total;
}

Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.