CONCEPT · Specialist
Minimum spanning tree
also Kruskal · Prim · MST
A minimum-total-weight set of n-1 edges that connects an undirected graph. Kruskal sorts and unions; Prim grows a cut. Disconnected input means no MST.
Intuition
The next lightest edge that does not cycle is safe (cut property). That one sentence is Kruskal.
When to reach for it
- CSES Road Reparation / Road Construction
- Minimize cable cost to connect cities
- Maximin path: MST then min edge on the unique tree path
Usual pits
- Printing a partial sum on a disconnected graph — return IMPOSSIBLE / -1
- Directed edges; you wanted an arborescence
- Calling a Dijkstra tree an MST
- int overflow on (n-1) * 1e9