Minimum Spanning Trees

You have an undirected connected graph with n vertices and weighted edges. A spanning tree uses n-1 edges, no cycles, and reaches everyone. The MST is a spanning tree of minimum total weight.

CSES Road Reparation is the drill. USACO Gold lists this next to DSU. Constraints: n, m ≤ 2·10⁵ means you sort edges (O(m log m)) and run DSU — you do not run Floyd–Warshall (O(n³)).

Kruskal with the DSU from the previous lessonjs

function mstWeight(n, edges) {
  edges = edges.slice().sort((a, b) => a[2] - b[2]);
  const p = Array.from({ length: n }, (_, i) => i);
  const r = Array(n).fill(0);
  const find = (x) => (p[x] === x ? x : (p[x] = find(p[x])));
  let weight = 0;
  let used = 0;
  for (const [u, v, w] of edges) {
    const a = find(u);
    const b = find(v);
    if (a === b) continue;
    if (r[a] < r[b]) p[a] = b;
    else if (r[a] > r[b]) p[b] = a;
    else {
      p[b] = a;
      r[a]++;
    }
    weight += w;
    used++;
  }
  return used === n - 1 ? weight : -1;
}

TRACE

n = 4. Edges (u,v,w): (0,1,1), (1,2,2), (0,2,4), (2,3,3), (0,3,10). Run Kruskal.

Sort

1, then 2, then 3, then 4, then 10.

weights 1 2 3 4 10

1 / 5

CHECK

Kruskal processed n-1 edges but find() still shows two roots. What happened?

Prim grows one tree: start at a vertex, always add the lightest edge leaving the tree (heap, O(m log n)). Same answer. Use Prim on dense graphs (m ≈ n²) with an O(n²) array; use Kruskal when edges are a list and you already have DSU.

WA modes:

- Directed edges. MST is undirected. A 'minimum arborescence' is a different algorithm. - 1-based ids into a size-n DSU. - Overflow: n-1 edges of weight 1e9 need 64-bit. - Using Dijkstra and calling it an MST. Shortest-path tree ≠ MST.

CHECK

When is the MST unique?

Checks 0/2

Next lesson