EF-T10: Minimum spanning forest

Exercise contract#

Given n >= 1 vertices labeled 0 through n-1 and undirected weighted edges (u,v,weight), return the minimum spanning-forest cost and the final number of connected components. Parallel edges, negative weights, and ties are allowed. Ignore self-loops because they never connect components. Reject malformed edges or endpoints outside the declared vertices.

Constraints

• 1 <= n <= 100,000 and 0 <= edges.length <= 200,000.
• Each weight is a signed 32-bit integer; the sum of selected weights fits a signed 64-bit integer.
• The forest spans every declared vertex, including isolated vertices.
• Only cost and component count are returned, so equal-cost forests need not expose a tie-specific edge order.

Examples

n=4, edges=[(0,1,3),(1,2,1),(0,2,5),(2,3,2),(1,3,4)]

{cost:6, components:1}Weights 1, 2, and 3 connect all four vertices without a cycle.

the same edges with n=5

{cost:6, components:2}Vertex 4 remains an isolated component, so the valid result is a forest rather than an error.

Derive the approach#

Baseline: Within each component, enumerate subsets of edges and retain the cheapest acyclic subset that connects its vertices. This establishes the objective but is exponential in the number of edges.

1. Sort edges by increasing weight. Self-loops can be skipped because their endpoints already have the same identity.
2. Maintain components with DSU. Accept an edge exactly when its endpoints currently have different representatives.
3. At that cut, a lightest crossing edge can be included in some minimum spanning forest; unioning prevents later cycles.
4. Add accepted weights in a wide accumulator and decrement the declared component count. Isolated vertices remain counted.

Time

O(m log m + (n + m) α(n))

Space

O(n + m) auxiliary space for DSU and the sorted edge records

Assumptions

m is the edge count; comparisons are constant-time; Java accumulates selected signed 32-bit weights in long and the promised total fits 64 bits.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def minimum_spanning_forest(n, edges):
    if n < 1:
        raise ValueError("n must be positive")
    normalized = []
    for index, edge in enumerate(edges):
        if len(edge) != 3:
            raise ValueError("each edge must contain u, v, weight")
        u, v, weight = edge
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("endpoint outside node range")
        normalized.append((weight, u, v, index))
    normalized.sort()
    parent, size = list(range(n)), [1] * n
    def find(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
    cost, components = 0, n
    for weight, u, v, _ in normalized:
        root_u, root_v = find(u), find(v)
        if root_u == root_v:
            continue
        if size[root_u] < size[root_v]:
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        cost += weight
        components -= 1
    return {"cost": cost, "components": components}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

record ForestResult(long cost, int components) {}
record Edge(int u, int v, int weight, int ordinal) {}

static ForestResult minimumSpanningForest(int n, int[][] rawEdges) {
    if (n < 1) throw new IllegalArgumentException("n must be positive");
    List<Edge> edges = new ArrayList<>();
    for (int index = 0; index < rawEdges.length; index++) {
        int[] edge = rawEdges[index];
        if (edge == null || edge.length != 3) throw new IllegalArgumentException("edge must have u, v, weight");
        if (edge[0] < 0 || edge[0] >= n || edge[1] < 0 || edge[1] >= n) throw new IllegalArgumentException("endpoint outside node range");
        edges.add(new Edge(edge[0], edge[1], edge[2], index));
    }
    edges.sort(Comparator.comparingInt(Edge::weight).thenComparingInt(Edge::u).thenComparingInt(Edge::v).thenComparingInt(Edge::ordinal));
    int[] parent = new int[n], size = new int[n];
    for (int node = 0; node < n; node++) { parent[node] = node; size[node] = 1; }
    long cost = 0;
    int components = n;
    for (Edge edge : edges) {
        int rootU = find(parent, edge.u()), rootV = find(parent, edge.v());
        if (rootU == rootV) continue;
        if (size[rootU] < size[rootV]) { int swap = rootU; rootU = rootV; rootV = swap; }
        parent[rootV] = rootU; size[rootU] += size[rootV];
        cost += (long) edge.weight();
        components--;
    }
    return new ForestResult(cost, components);
}

static int find(int[] parent, int node) {
    while (parent[node] != node) { parent[node] = parent[parent[node]]; node = parent[node]; }
    return node;
}

Deterministic test plan#

Transfer and follow-ups#

• Return the selected forest edges using the same deterministic sorted order.
• Explain why a shortest-path tree and a minimum spanning tree optimize different objectives.

Contrast the spanning-forest objective with source-to-vertex shortest paths before choosing an algorithm.

Authorship and review#

An original Engineering Foundry exercise using the standard Kruskal/DSU technique; it is not company-tagged or presented as a proprietary prompt.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09