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 processes undirected edges from cheapest upward. Accept an edge only when its endpoints currently belong to different components. A disjoint-set structure makes that connectivity query cheap.

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.

parent := []int{0, 0, 0, 3} // Buildings 0, 1, 2 are already connected.
find := func(vertex int) int {
	for parent[vertex] != vertex {
		parent[vertex] = parent[parent[vertex]]
		vertex = parent[vertex]
	}
	return vertex
}
fmt.Println(find(0) == find(2)) // true: reject the triangle's extra edge.
a, b := find(2), find(3)
if a != b {
	parent[b] = a
} // Here the single-node component joins the larger one.
fmt.Println(find(3) == find(0)) // true: building 3 is now connected.

Keeping component links separate from cables

Union by size/rank and path compression keep DSU paths short. Join roots rather than arbitrary endpoints. DSU parent links are bookkeeping, not the chosen graph edges. The cut property justifies each accepted cheapest connection; negative weights do not invalidate it. Build private working state. The Go API uses nil for absence and assumes finite cost arithmetic fits int.

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.

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