Minimum spanning tree (Kruskal)
Sort the edges by weight and keep those that join two different components. , 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 to , 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 .
Pitfalls
- In
Road Reparationthe answer isIMPOSSIBLEwhen the graph is disconnected. That is the "count the edges" above. - Weights add up in
long long: edges times .
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// 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.
- Road Reparation · Graph Algorithms
More in the USACO Guide
- Minimum Spanning Trees · usaco.guide/gold/mst
In English, with more problems per level.