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

Build a canonical minimum spanning tree for an undirected graph, allowing negative costs and ignoring self-loops. A cheapest edge is useful only when it connects different components.

Sorting edges and checking connectivity by traversing accepted edges is a clear baseline. DSU stores component membership so cycle checks do not repeatedly search the growing tree. Normalize endpoint orientation before tie-breaking.

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.

Kruskal selects the next cheapest edge that crosses components. DSU represents component identity, while path compression and union by rank reduce repeated connectivity checks. Normalize endpoints before sorting so orientation cannot alter the canonical answer. Final O(E log E) sorting plus near-linear DSU work and O(V+E) storage.

Normalization makes two orientations of the same undirected edge compare consistently:

import java.util.*;

class Example {
    public static void main(String[] args) {
        int from = 7, to = 2;
        int low = Math.min(from, to), high = Math.max(from, to);
        assert low == 2 && high == 7;
        assert low == Math.min(to, from);
        assert high == Math.max(to, from);
    }
}

Weight remains the primary ordering key, followed by these normalized endpoints. DSU roots represent connectivity, not accepted-edge output order. A result with fewer than n-1 accepted edges is disconnected, even if several cheap cycles were considered.

Keeping component links separate from cables

MST construction is useful for cheapest connectivity under an undirected cost model. It minimizes total connection cost, not source-to-vertex route distances; shortest-path and spanning-tree objectives differ.

Undirected weights may be negative. Normalize edges to min/max endpoints, then process by weight/from/to, rejecting self-loops and cycles. Return Mst(totalCost, acceptedEdges) in acceptance order, or null when disconnected. Valid n=0/1 returns cost zero and empty edges. Reject negative n or invalid endpoints.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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