Kruskal and disjoint sets

A campus needs cables connecting every building, and contractors have quoted costs for possible links. The objective is the total installation bill, not the shortest route from the entrance to each building.

Taking the cheapest links blindly can buy a cheap cycle while leaving a building isolated. Kruskal considers links in cost order but accepts one only when it joins two currently separate components. Union-find makes that connectivity check cheap.

Connecting every building on a budget

Kruskal chooses the cheapest edge joining different current components. A disjoint-set structure answers that connectivity question without repeatedly traversing the accepted forest. Path compression shortens future find paths; union by size bounds tree growth.

Rejecting a cheap edge that closes a cycle

For links 0–1:1, 1–2:2, 0–2:3, and 2–3:4, accept the first two and reject the third: it only closes the existing triangle. The last link reaches building 3, bringing the bill to seven. DSU representatives answer whether endpoints are already connected; their parent pointers are bookkeeping and are not the cables selected for the result.

std::vector<std::size_t> parent{0, 0, 0, 3};
auto find = [&parent](std::size_t vertex) {
    while (parent[vertex] != vertex) {
        parent[vertex] = parent[parent[vertex]];
        vertex = parent[vertex];
    }
    return vertex;
};
std::cout << std::boolalpha << (find(0) == find(2)) << '\n'; // true: a cycle.
auto a = find(2), b = find(3);
if (a != b) parent[b] = a; // Attach this single-node component to the larger one.
std::cout << (find(3) == find(0)) << '\n'; // true: all four are connected.
// Keep the accepted cable edges separately from these parent links.

Keeping component links separate from cables

This distinction between storage format and sort key is observable when weights tie. Normalize orientation before sorting, and append edges in acceptance order. Self-loops always connect a component to itself. Negative costs are valid because the cycle-cut argument does not require positive weights. A connected n-vertex tree needs n-1 accepted edges; otherwise return absence rather than a minimum spanning forest. Validate endpoints even when n is zero or one. Sorting dominates at O(E log E), with almost-constant amortized DSU operations.

Sorting costs O(E log(E+1)); initializing components costs O(V). Path compression and size/rank balancing make DSU operations amortized inverse-Ackermann time. Searching the accepted forest for every candidate is a useful slower reference. A disconnected graph has no spanning tree, even if its cheapest local links look convincing.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

The cable plan consists of the accepted graph edges, never the DSU parent links used to choose them.