Kruskal (MST)
O(m log m)Minimum spanning tree: sort edges by weight and add each one that connects two different components. Needs the DSU template (paste it above this). If fewer than n−1 edges get added, the graph is disconnected.
// use it on
CSES: Road Reparation ↗
Minimum cost to connect all cities, or report impossible. That is the MST cost plus the connectivity check on the last line.
// the code
// requires the DSU template; edges as {w, u, v}
long long kruskal(int n, vector<array<long long, 3>>& edges) {
sort(edges.begin(), edges.end());
DSU dsu(n);
long long cost = 0;
int used = 0;
for (auto& [w, u, v] : edges)
if (dsu.unite(u, v)) {
cost += w;
used++;
}
return used == n - 1 ? cost : -1; // -1 = graph not connected
}// more spanning trees