Second-Best Minimum Spanning Tree — Interview Preparation¶

The second-best MST is a high-signal interview topic: it tests whether you truly understand MST structure (cut/cycle properties), whether you can reason about edge swaps, and whether you handle the notorious equal-weight tie. The very same machinery powers "critical and pseudo-critical edges" — a popular hard problem. This file is a curated bank of questions by seniority, behavioral prompts, and runnable Go/Java/Python coding challenges.

Quick-Reference Cheat Sheet¶

For each non-tree edge (u, v, w):
    (m1, m2) = pathMaxAndSecondMax(u, v)   # over MST path
    if   w >  m1: delta = w - m1
    elif w == m1: delta = 0
    elif m2 != -inf: delta = w - m2
    else: skip
answer = MST_weight + min(delta)

Junior Questions (12 Q&A)¶

J1. What is a second-best minimum spanning tree?¶

It is the spanning tree of minimum total weight among all spanning trees that are not the MST. If the MST is unique, the second-best is strictly heavier; if several MSTs share the minimum weight, the second-best weighs the same as the MST. It is the natural "runner-up" to the optimal network.

J2. By how many edges does the second-best MST differ from the MST?¶

By exactly one. You add one non-tree edge and remove one tree edge. This "single edge swap" fact is what makes the problem tractable — you only have E − (V−1) candidate swaps to consider, one per non-tree edge.

J3. Why does adding a non-tree edge to the MST create a cycle?¶

Because the MST already connects every pair of vertices through a unique tree path. Adding an edge (u, v) that is not in the tree gives a second route between u and v, closing exactly one cycle — the tree path u ⇝ v plus the new edge. This is the "fundamental cycle" of that edge.

J4. For a fixed non-tree edge, which tree edge should you remove?¶

The maximum-weight edge on the MST path between the edge's endpoints. The new tree's weight is MST − w(removed) + w(added); to make it smallest you remove the heaviest removable edge.

J5. What is the formula for the second-best MST weight?¶

MST_weight + min over all non-tree edges (u,v,w) of (w − maxPathEdge(u,v)), where maxPathEdge is the heaviest edge on the MST path between u and v. You take the smallest such delta across all non-tree edges.

J6. What goes wrong if a non-tree edge has the same weight as the path-max?¶

Then w − max = 0, meaning a different spanning tree of the same total weight. That is a valid second-best MST (it proves multiple MSTs exist). If your code only handles w > max, you miss this case and report a too-large answer.

J7. Why might you need the second-maximum edge on the path?¶

To form a tree distinct from the MST when you cannot or should not remove the path-maximum — for example, when the path-max edge equals the non-tree edge and you want a strictly different weight, or in constrained variants where the max edge is forced to stay. The second-max is the largest path edge strictly below the maximum.

J8. What is the time complexity of the standard algorithm?¶

O((V + E) log V): O(E log E) to build the MST with Kruskal, O(V log V) to build the LCA binary-lifting tables, and O(log V) per non-tree edge to query the path-max, over O(E) edges.

J9. What does the naive approach cost and why avoid it?¶

Naively, for each non-tree edge you walk the tree path and scan for the maximum in O(V), giving O(E·V). For V = E = 10⁵ that is 10¹⁰ operations — far too slow. The LCA method replaces the O(V) walk with an O(log V) query.

J10. What if the graph is disconnected?¶

Then there is no spanning tree at all, so neither an MST nor a second-best MST exists. Kruskal will finish with fewer than V − 1 edges; detect that (cnt < V − 1) and return a sentinel ("no spanning tree").

J11. What if the graph is already a tree?¶

Every edge is a tree edge and there are no non-tree edges, so no swap is possible and no second-best MST exists. The minimum-delta loop finds no candidate; return a sentinel.

J12 (analysis). Why is exactly one swap always sufficient?¶

Take the MST T* and the second-best T₂. If they differed by two or more swaps, you could perform just the single cheapest swap (introducing the lightest new edge), producing a spanning tree that is different from T* and no heavier than T₂. By definition T₂ is the lightest tree different from T*, so this single-swap tree is also optimal. Hence some optimal second-best is one swap away, and searching all single swaps finds it.

Middle Questions (12 Q&A)¶

M1. Walk through the full algorithm step by step.¶

Build the MST with Kruskal, recording which edges are tree edges and constructing the MST adjacency list. Root the MST and build binary-lifting tables storing, per 2^k jump, the first and second maximum edge weight. For each non-tree edge (u,v,w), query the path-max m1 and second-max m2; compute delta by the three-branch rule; track the minimum. Output MST_weight + min_delta.

M2. How do you compute the path-maximum with binary lifting?¶

Store up[k][v] (the 2^k-th ancestor), mx1[k][v], mx2[k][v] (first/second max edge on that 2^k climb). To query (u, v), lift the deeper node up to equalize depths (aggregating maxima), then lift both nodes together until their parents meet, aggregating along the way, then take one final step to the LCA. Each query touches O(log V) levels.

M3. Why track a second maximum and not just the maximum?¶

Because two equal maxima must collapse to one distinct "first." The merge of two (first, second) pairs returns the two largest distinct values, so when the path has edges {5, 5, 3} the pair is (5, 3), not (5, 5). The second value is the largest weight strictly below the first, which is what the w < max and constrained cases need.

M4. How is this related to "critical and pseudo-critical edges"?¶

An MST edge is critical if removing it increases the MST weight (it is in every MST); an edge is pseudo-critical if it appears in some MST but is not critical. You decide criticality with the same path-max idea: an edge (u,v,w) is non-critical iff its fundamental cut has another edge of equal weight. The standard solution forces each edge in/out and recomputes the MST weight — same building blocks.

M5. When would you choose heavy-light decomposition over binary lifting?¶

When edge weights change between queries (dynamic sensitivity analysis). HLD with a segment tree over chains supports point-update of an edge weight in O(log² V) and path-max query in O(log² V), whereas binary lifting tables must be fully rebuilt on any change. For a static tree, binary lifting is simpler and faster.

M6. How do you handle multiple MSTs of equal weight?¶

They are exactly the case where the second-best weight equals the MST weight. A non-tree edge whose weight equals its path-max yields delta = 0, so min_delta = 0 and the second-best equals the MST. This is correct behavior and also serves as an MST-uniqueness test.

M7. Is w(e) < pathMax ever possible for a real MST?¶

No. By the cycle property, for every non-tree edge e, w(e) is a maximum (possibly tied) edge of its fundamental cycle, so w(e) ≥ pathMax. The w < max branch is unreachable for the unconstrained second-best; it is retained for constrained/k-best variants where the path-max edge is forced to remain in the tree.

M8. How would you also report which edges to swap, not just the weight?¶

Track, alongside the minimum delta, the index of the entering non-tree edge and the weight (or identity) of the removed path edge. To recover the exact removed edge you can store, in the lifting tables, the edge identity achieving the maximum, or re-walk the single winning path once at the end.

M9. How do you extend to "cheapest network if a specific link f fails"?¶

For a given tree edge f, the cheapest reconnection is the lightest non-tree edge whose fundamental cycle passes through f. Precompute, for each tree edge, the minimum-weight covering non-tree edge — one sweep over non-tree edges, marking the path each covers (small-to-large merging or a tree-difference array).

M10. What is the k-best generalization and where does the single-swap argument break?¶

The k-best spanning trees are the k lightest. The single-swap argument only links the MST and the second-best (k = 2). For k ≥ 3, the third-best may be two swaps from the MST. You then use Eppstein/Gabow branching: a priority queue of constrained subproblems, each solved by a constrained best-swap (which is why the second-max rule matters).

M11. Why root the tree before building the lifting tables?¶

Path queries and LCA require a rooted tree to define ancestors, depths, and the 2^k-th ancestor. The MST is undirected; rooting it (say at vertex 0 via DFS/BFS) assigns each edge to the deeper endpoint, letting mx1[0][v] store the weight of the edge from v to its parent.

M12 (analysis). What is the space cost and how do you reduce it?¶

Binary lifting uses O(V log V) for up, mx1, mx2. At V = 10⁶ that is ~240 MB. To reduce, use an Euler tour + sparse table (LCA in O(1) with O(V log V) over Euler edges) or a Kruskal reconstruction tree (O(V) extra), trading some code complexity for lower memory.

Senior Questions (10 Q&A)¶

S1. Prove the single-edge-swap theorem informally.¶

Spanning trees are bases of the graphic matroid, which satisfies the strong exchange property: any two bases are connected by single-element swaps that each keep a basis. Order these swaps by the entering edge's weight; the cheapest single swap from T* produces a distinct spanning tree no heavier than the full multi-swap target. Since the second-best is the lightest tree different from T*, one swap attains it.

S2. Why is removing the path-maximum optimal for a fixed entering edge?¶

The swap weight is MST − w(f) + w(e); only w(f) varies and ranges over the path edges. Minimizing the total maximizes w(f), i.e. picks the path-maximum. Every choice of f on the path yields a valid spanning tree (the removed edge separates the endpoints, the new edge reconnects them).

S3. How does the second-best computation double as an MST-uniqueness test?¶

w(second-best) > w(MST) iff the MST is unique. Equivalently, if the minimum swap delta is 0, there is a distinct equal-weight tree, so the MST is non-unique; if it is strictly positive, the MST is unique with that positive margin as the quantified gap.

S4. Which path-query engine would you pick for V = 10⁷ static, batch queries?¶

Not binary lifting (memory). Use a Kruskal reconstruction tree with offline DSU path-max (O(α) per query, O(V) extra space) or an Euler tour + sparse table. For the theoretically optimal route, King/Komlós tree-path-maximum answers all queries in O(m α(m,n)) total.

S5. How do you keep the answer fresh as edge costs drift in production?¶

For weight-only changes on a fixed topology, maintain an HLD and update changed edges in O(log² V), recomputing second-best contributions only for affected paths; full-rebuild periodically. For topology changes, you are in fully-dynamic-MST territory (Holm–de Lichtenberg–Thorup) — usually approximated by periodic recompute plus event-triggered refresh.

S6. What metrics would you surface from a second-best computation in a network-planning service?¶

robustness = second/MST (gap to the nearest alternative), swap_delta_min (absolute extra cost), tie_count (how many equally good fallbacks), critical_edge_count (irreplaceable links), and a per_link_backup table (cheapest reconnection per tree edge). The last converts theory into an operations runbook.

S7. What are the main production failure modes?¶

The silent equal-weight bug (shipping only the w > max branch), disconnected input treated as connected, stale answers after topology changes, 32-bit overflow on summed weights, and O(V log V) table memory blow-up at very large V. Guard with a tie-heavy brute-force fuzzer in CI.

S8. How does this connect to the cut and cycle properties?¶

The cut property (the unique lightest edge across any cut is in every MST) and the cycle property (the unique heaviest edge on any cycle is in no MST) justify both Kruskal and the swap logic: w(e) ≥ pathMax for non-tree edges follows directly from the cycle property on the fundamental cycle.

S9. How would you parallelize or distribute the computation?¶

Build the MST with a distributed Borůvka-style algorithm, then partition path-max queries: queries within a cluster use a local engine; cross-cluster swaps are evaluated separately. If the graph decomposes into weakly connected clusters, compute per-cluster second-best in parallel and reconcile inter-cluster links.

S10 (analysis). What is the theoretically optimal complexity once the MST is known?¶

O(m α(m, n)). All m fundamental-cycle path-maximum queries are answerable in near-linear total time via the Komlós / King tree-path-maximum technique — the same primitive behind linear-time MST verification (Dixon–Rauch–Tarjan). Binary lifting's O(m log n) is simpler but a log n factor away from this optimum.

Professional Questions (8 Q&A)¶

P1. Design a network-robustness service around second-best MST.¶

A batch pipeline: ingest the cost feed, build the MST, build one path-max engine, then emit the second-best weight, per-link backup table, and robustness score to a store behind an API. Keep MST builder, path engine, and swap evaluator as separate components so one engine instance serves all robustness queries. Add recompute_age to track staleness against the live feed.

P2. How do you validate correctness before shipping?¶

Property-based testing against a brute-force enumerator on small graphs (n ≤ 7), with weights drawn from a tiny range to force frequent ties — the equal-weight case is where every real bug lives. The reference implementation passed 3738 such cases with zero discrepancies; the tie-blind variant failed 726. Keep this fuzzer in CI.

P3. When do you choose the offline Kruskal-reconstruction-tree route over online binary lifting?¶

When all queries are known up front, E is very large, and memory is tight. The reconstruction tree answers path-max in O(α) after an O(E log E) build with O(V) extra space, versus binary lifting's O(V log V) tables and O(log V) queries. Online or streaming query patterns favor binary lifting or HLD.

P4. How do you compute per-link backup costs efficiently?¶

For each tree edge f, you want the lightest non-tree edge whose fundamental cycle covers f. Sweep non-tree edges in increasing weight; each covers a tree path; assign it as the backup to every still-unassigned tree edge on that path using a union-find "jump to next unassigned" trick or small-to-large path marking, giving near-linear total time.

P5. How would you support the k cheapest alternative networks for a planning UI?¶

Use Eppstein/Gabow branching: maintain a priority queue of subproblems, each constraining some edges in and some out; expand the cheapest by computing its best constrained swap (the M₁/M₂ rule with forced edges). Pop k times to emit the k lightest distinct spanning trees in order, letting field teams pick by secondary criteria.

P6. How do you handle a graph that loses connectivity at runtime?¶

Detect cnt < V − 1 after the MST phase and emit a distinct "no spanning tree" status rather than a numeric answer. For per-component analysis, run the algorithm independently on each connected component and report which components are unspanned.

P7. What overflow and numerical concerns exist?¶

MST weights sum over V − 1 possibly large edges — use 64-bit accumulators. Deltas are differences of edge weights and stay small, but the base weight does not. If weights are floating point, define tie-handling with an epsilon and be aware that strict equality (w == max) becomes fragile; integer weights are strongly preferred.

P8 (analysis). Why retain the unreachable w < max branch in production code?¶

Because the same routine answers constrained best-swap queries (k-best, "edge forced out") where the path-maximum edge cannot be removed, making the largest removable edge the second-maximum. Keeping the full three-branch rule costs nothing, makes the routine robust to being called on a non-minimum base tree, and avoids a rewrite when generalizing to k-best.

Behavioral / System-Design Questions (5 short)¶

B1. Tell me about a time you had to justify a "second-best" or fallback design over the optimal one.¶

Look for a story with a real constraint (a link could not be used, a vendor pulled out, a region failed) where the optimal plan was infeasible and the candidate quantified the cost of the next-best option. Strong answers cite the actual delta ("the backup was 12% more expensive") and how that number drove the decision.

B2. Design a service that tells planners how robust their network layout is.¶

Second-best MST plus per-link backups is the core. Discuss the cost feed, recompute cadence, what "robustness" means to a non-engineer (the gap to the nearest alternative), and how you would alert when robustness drops (many equal plans) or spikes (a single failure becomes very costly). Cover staleness, disconnection, and overflow.

B3. A teammate's MST sensitivity code gives wrong answers only sometimes. How do you debug it?¶

The classic culprit is the equal-weight tie: the code handles w > max but not w == max, so it fails exactly when weights repeat. Reproduce with a brute-force checker on small tie-heavy graphs, confirm the failing inputs all have ties, then add the delta = 0 branch. Add the fuzzer to CI so it cannot regress.

B4. A junior asks why you do not just rebuild the MST for every "what if this edge fails" question. How do you respond?¶

Rebuilding is O(E log E) per question; with E such questions that is O(E² log E). Building one path-max engine answers each question in O(log V). Use it as a teaching moment about precomputation and about separating the expensive one-time build from cheap repeated queries.

B5. How would you explain "the second-best equals the best" to a stakeholder?¶

Say: "There are two equally cheap layouts. That is good news — if one link is blocked, we can switch to an equally priced alternative for free. It also means there is no single 'uniquely optimal' plan to defend; several are tied." Frame the tie as resilience, not ambiguity.

Coding Challenges¶

Challenge 1: Second-Best MST Weight¶

Problem. Given a connected, weighted, undirected graph with n vertices and a list of edges (u, v, w), return the weight of the second-best minimum spanning tree — the minimum-weight spanning tree different from the MST. If the graph is a tree (no alternative exists), return -1.

Example.

n = 5
edges = [(0,1,1),(1,2,2),(2,3,3),(3,4,4),(1,3,5),(0,4,6)]
MST weight = 10  (the path 0-1-2-3-4)
second-best = 12 (add (1,3,5) or (0,4,6), remove a weight-3 or weight-4 path edge)

Brute force. Enumerate all C(E, V−1) edge subsets, keep spanning trees, find the MST weight and the minimum weight strictly different from the chosen MST. Exponential — only for verification.

Optimal. Build the MST, then for each non-tree edge compute the swap delta against the path first/second-max via LCA binary lifting. O((V+E) log V).

Go.

package main

import (
    "fmt"
    "sort"
)

const NEG = -1 << 60

type Edge struct{ u, v, w int }

func merge(a1, a2, b1, b2 int) (int, int) {
    first := a1
    if b1 > first {
        first = b1
    }
    second := NEG
    for _, x := range []int{a1, a2, b1, b2} {
        if x < first && x > second {
            second = x
        }
    }
    return first, second
}

var (
    LOG      int
    up       [][]int
    mx1, mx2 [][]int
    depth    []int
)

func buildLCA(n int, adj [][][2]int) {
    LOG = 1
    for (1 << LOG) < n {
        LOG++
    }
    LOG++
    up = make([][]int, LOG)
    mx1 = make([][]int, LOG)
    mx2 = make([][]int, LOG)
    depth = make([]int, n)
    for k := 0; k < LOG; k++ {
        up[k] = make([]int, n)
        mx1[k] = make([]int, n)
        mx2[k] = make([]int, n)
        for i := 0; i < n; i++ {
            mx1[k][i], mx2[k][i] = NEG, NEG
        }
    }
    seen := make([]bool, n)
    st := []int{0}
    seen[0] = true
    for len(st) > 0 {
        x := st[len(st)-1]
        st = st[:len(st)-1]
        for _, e := range adj[x] {
            v, w := e[0], e[1]
            if !seen[v] {
                seen[v] = true
                depth[v] = depth[x] + 1
                up[0][v] = x
                mx1[0][v] = w
                st = append(st, v)
            }
        }
    }
    for k := 1; k < LOG; k++ {
        for v := 0; v < n; v++ {
            mid := up[k-1][v]
            up[k][v] = up[k-1][mid]
            mx1[k][v], mx2[k][v] = merge(mx1[k-1][v], mx2[k-1][v], mx1[k-1][mid], mx2[k-1][mid])
        }
    }
}

func query(u, v int) (int, int) {
    m1, m2 := NEG, NEG
    if depth[u] < depth[v] {
        u, v = v, u
    }
    d := depth[u] - depth[v]
    for k := 0; k < LOG; k++ {
        if (d>>k)&1 == 1 {
            m1, m2 = merge(m1, m2, mx1[k][u], mx2[k][u])
            u = up[k][u]
        }
    }
    if u == v {
        return m1, m2
    }
    for k := LOG - 1; k >= 0; k-- {
        if up[k][u] != up[k][v] {
            m1, m2 = merge(m1, m2, mx1[k][u], mx2[k][u])
            m1, m2 = merge(m1, m2, mx1[k][v], mx2[k][v])
            u, v = up[k][u], up[k][v]
        }
    }
    m1, m2 = merge(m1, m2, mx1[0][u], mx2[0][u])
    m1, m2 = merge(m1, m2, mx1[0][v], mx2[0][v])
    return m1, m2
}

func secondBest(n int, edges []Edge) int {
    idx := make([]int, len(edges))
    for i := range idx {
        idx[i] = i
    }
    sort.Slice(idx, func(a, b int) bool { return edges[idx[a]].w < edges[idx[b]].w })
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    inMST := make([]bool, len(edges))
    adj := make([][][2]int, n)
    mstW, cnt := 0, 0
    for _, i := range idx {
        e := edges[i]
        ru, rv := find(e.u), find(e.v)
        if ru != rv {
            parent[ru] = rv
            inMST[i] = true
            mstW += e.w
            cnt++
            adj[e.u] = append(adj[e.u], [2]int{e.v, e.w})
            adj[e.v] = append(adj[e.v], [2]int{e.u, e.w})
        }
    }
    if cnt != n-1 {
        return -1
    }
    buildLCA(n, adj)
    best := 1 << 60
    for i, e := range edges {
        if inMST[i] {
            continue
        }
        m1, m2 := query(e.u, e.v)
        var delta int
        switch {
        case e.w > m1:
            delta = e.w - m1
        case e.w == m1:
            delta = 0
        case m2 != NEG:
            delta = e.w - m2
        default:
            continue
        }
        if delta < best {
            best = delta
        }
    }
    if best == 1<<60 {
        return -1
    }
    return mstW + best
}

func main() {
    edges := []Edge{{0, 1, 1}, {1, 2, 2}, {2, 3, 3}, {3, 4, 4}, {1, 3, 5}, {0, 4, 6}}
    fmt.Println(secondBest(5, edges)) // 12
}

Java.

import java.util.*;

public class SecondBestWeight {
    static final int NEG = Integer.MIN_VALUE / 4;
    static int LOG;
    static int[][] up, mx1, mx2;
    static int[] depth;

    static int[] merge(int a1, int a2, int b1, int b2) {
        int first = Math.max(a1, b1), second = NEG;
        for (int x : new int[]{a1, a2, b1, b2})
            if (x < first && x > second) second = x;
        return new int[]{first, second};
    }

    static void buildLCA(int n, List<int[]>[] adj) {
        LOG = 1;
        while ((1 << LOG) < n) LOG++;
        LOG++;
        up = new int[LOG][n];
        mx1 = new int[LOG][n];
        mx2 = new int[LOG][n];
        depth = new int[n];
        for (int[] r : mx1) Arrays.fill(r, NEG);
        for (int[] r : mx2) Arrays.fill(r, NEG);
        boolean[] seen = new boolean[n];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(0);
        seen[0] = true;
        while (!st.isEmpty()) {
            int x = st.pop();
            for (int[] e : adj[x])
                if (!seen[e[0]]) {
                    seen[e[0]] = true;
                    depth[e[0]] = depth[x] + 1;
                    up[0][e[0]] = x;
                    mx1[0][e[0]] = e[1];
                    st.push(e[0]);
                }
        }
        for (int k = 1; k < LOG; k++)
            for (int v = 0; v < n; v++) {
                int mid = up[k - 1][v];
                up[k][v] = up[k - 1][mid];
                int[] m = merge(mx1[k - 1][v], mx2[k - 1][v], mx1[k - 1][mid], mx2[k - 1][mid]);
                mx1[k][v] = m[0];
                mx2[k][v] = m[1];
            }
    }

    static int[] query(int u, int v) {
        int m1 = NEG, m2 = NEG;
        if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
        int d = depth[u] - depth[v];
        for (int k = 0; k < LOG; k++)
            if (((d >> k) & 1) == 1) {
                int[] m = merge(m1, m2, mx1[k][u], mx2[k][u]);
                m1 = m[0]; m2 = m[1];
                u = up[k][u];
            }
        if (u == v) return new int[]{m1, m2};
        for (int k = LOG - 1; k >= 0; k--)
            if (up[k][u] != up[k][v]) {
                int[] a = merge(m1, m2, mx1[k][u], mx2[k][u]);
                int[] b = merge(a[0], a[1], mx1[k][v], mx2[k][v]);
                m1 = b[0]; m2 = b[1];
                u = up[k][u]; v = up[k][v];
            }
        int[] a = merge(m1, m2, mx1[0][u], mx2[0][u]);
        int[] b = merge(a[0], a[1], mx1[0][v], mx2[0][v]);
        return new int[]{b[0], b[1]};
    }

    static int[] par;
    static int find(int x) { while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; } return x; }

    static long secondBest(int n, int[][] edges) {
        Integer[] idx = new Integer[edges.length];
        for (int i = 0; i < idx.length; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Integer.compare(edges[a][2], edges[b][2]));
        par = new int[n];
        for (int i = 0; i < n; i++) par[i] = i;
        boolean[] inMST = new boolean[edges.length];
        List<int[]>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        long mstW = 0; int cnt = 0;
        for (int i : idx) {
            int ru = find(edges[i][0]), rv = find(edges[i][1]);
            if (ru != rv) {
                par[ru] = rv; inMST[i] = true; mstW += edges[i][2]; cnt++;
                adj[edges[i][0]].add(new int[]{edges[i][1], edges[i][2]});
                adj[edges[i][1]].add(new int[]{edges[i][0], edges[i][2]});
            }
        }
        if (cnt != n - 1) return -1;
        buildLCA(n, adj);
        long best = Long.MAX_VALUE;
        for (int i = 0; i < edges.length; i++) {
            if (inMST[i]) continue;
            int[] m = query(edges[i][0], edges[i][1]);
            int w = edges[i][2];
            long delta;
            if (w > m[0]) delta = w - m[0];
            else if (w == m[0]) delta = 0;
            else if (m[1] != NEG) delta = w - m[1];
            else continue;
            best = Math.min(best, delta);
        }
        return best == Long.MAX_VALUE ? -1 : mstW + best;
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1,1},{1,2,2},{2,3,3},{3,4,4},{1,3,5},{0,4,6}};
        System.out.println(secondBest(5, edges)); // 12
    }
}

Python.

from typing import List, Tuple

NEG = float("-inf")


def merge(a1, a2, b1, b2):
    vals = sorted([a1, a2, b1, b2], reverse=True)
    first = vals[0]
    for x in vals[1:]:
        if x < first:
            return first, x
    return first, NEG


def second_best(n: int, edges: List[Tuple[int, int, int]]) -> int:
    order = sorted(range(len(edges)), key=lambda i: edges[i][2])
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    in_mst = [False] * len(edges)
    adj: List[List[Tuple[int, int]]] = [[] for _ in range(n)]
    mst_w = cnt = 0
    for i in order:
        u, v, w = edges[i]
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            in_mst[i] = True
            mst_w += w
            cnt += 1
            adj[u].append((v, w))
            adj[v].append((u, w))
    if cnt != n - 1:
        return -1

    LOG = max(1, n.bit_length()) + 1
    up = [[0] * n for _ in range(LOG)]
    mx1 = [[NEG] * n for _ in range(LOG)]
    mx2 = [[NEG] * n for _ in range(LOG)]
    depth = [0] * n
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        x = stack.pop()
        for v, w in adj[x]:
            if not seen[v]:
                seen[v] = True
                depth[v] = depth[x] + 1
                up[0][v] = x
                mx1[0][v] = w
                stack.append(v)
    for k in range(1, LOG):
        for v in range(n):
            mid = up[k - 1][v]
            up[k][v] = up[k - 1][mid]
            mx1[k][v], mx2[k][v] = merge(mx1[k - 1][v], mx2[k - 1][v], mx1[k - 1][mid], mx2[k - 1][mid])

    def query(u, v):
        m1 = m2 = NEG
        if depth[u] < depth[v]:
            u, v = v, u
        d = depth[u] - depth[v]
        for k in range(LOG):
            if (d >> k) & 1:
                m1, m2 = merge(m1, m2, mx1[k][u], mx2[k][u])
                u = up[k][u]
        if u == v:
            return m1, m2
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                m1, m2 = merge(m1, m2, mx1[k][u], mx2[k][u])
                m1, m2 = merge(m1, m2, mx1[k][v], mx2[k][v])
                u, v = up[k][u], up[k][v]
        m1, m2 = merge(m1, m2, mx1[0][u], mx2[0][u])
        m1, m2 = merge(m1, m2, mx1[0][v], mx2[0][v])
        return m1, m2

    best = float("inf")
    for i, (u, v, w) in enumerate(edges):
        if in_mst[i]:
            continue
        m1, m2 = query(u, v)
        if w > m1:
            delta = w - m1
        elif w == m1:
            delta = 0
        elif m2 != NEG:
            delta = w - m2
        else:
            continue
        best = min(best, delta)
    return mst_w + best if best != float("inf") else -1


if __name__ == "__main__":
    edges = [(0, 1, 1), (1, 2, 2), (2, 3, 3), (3, 4, 4), (1, 3, 5), (0, 4, 6)]
    print(second_best(5, edges))  # 12

Follow-up. What if you must also return the actual swap (which edge enters, which leaves)? Track the winning non-tree edge index and the removed path edge alongside the minimum delta; recover the exact removed edge by re-walking the single winning path or by storing edge identities in the lifting tables.

Challenge 2: Find Critical and Pseudo-Critical Edges in an MST¶

Problem. Given a connected weighted undirected graph (n nodes, edges [u, v, w] with indices), return two lists: the indices of all critical edges (in every MST) and all pseudo-critical edges (in some MST but not all). (LeetCode 1489.)

Example.

n = 5
edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
critical = [0, 1]          (the two weight-1 edges are in every MST)
pseudo   = [2, 3, 4, 5]    (ties give choices)

Approach. Compute the base MST weight. For each edge: if forcing it out raises the MST weight (or disconnects), it is critical. Otherwise, if forcing it in still yields the base weight, it is pseudo-critical. Each MST recompute is O(E α); total O(E² α), fine for the constraint E ≤ 200.

Go.

package main

import (
    "fmt"
    "sort"
)

type E struct{ u, v, w, id int }

func mstWeight(n int, es []E, skip, force int) int {
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    union := func(a, b int) bool {
        ra, rb := find(a), find(b)
        if ra == rb {
            return false
        }
        parent[ra] = rb
        return true
    }
    w, cnt := 0, 0
    if force != -1 {
        union(es[force].u, es[force].v)
        w += es[force].w
        cnt++
    }
    for i, e := range es {
        if i == skip || i == force {
            continue
        }
        if union(e.u, e.v) {
            w += e.w
            cnt++
        }
    }
    if cnt != n-1 {
        return 1 << 60
    }
    return w
}

func findCriticalAndPseudo(n int, edges [][]int) [][]int {
    es := make([]E, len(edges))
    for i, e := range edges {
        es[i] = E{e[0], e[1], e[2], i}
    }
    sort.Slice(es, func(a, b int) bool { return es[a].w < es[b].w })
    base := mstWeight(n, es, -1, -1)
    var crit, pseudo []int
    pos := make([]int, len(edges))
    for j, e := range es {
        pos[e.id] = j
    }
    for id := 0; id < len(edges); id++ {
        j := pos[id]
        if mstWeight(n, es, j, -1) > base {
            crit = append(crit, id)
        } else if mstWeight(n, es, -1, j) == base {
            pseudo = append(pseudo, id)
        }
    }
    sort.Ints(crit)
    sort.Ints(pseudo)
    return [][]int{crit, pseudo}
}

func main() {
    edges := [][]int{{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2}, {0, 4, 3}, {3, 4, 3}, {1, 4, 6}}
    r := findCriticalAndPseudo(5, edges)
    fmt.Println(r[0], r[1]) // [0 1] [2 3 4 5]
}

Java.

import java.util.*;

public class CriticalEdges {
    static int[] par;
    static int find(int x) { while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; } return x; }
    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        par[ra] = rb; return true;
    }

    static int mstWeight(int n, int[][] es, int skip, int force) {
        par = new int[n];
        for (int i = 0; i < n; i++) par[i] = i;
        int w = 0, cnt = 0;
        if (force != -1) { union(es[force][0], es[force][1]); w += es[force][2]; cnt++; }
        for (int i = 0; i < es.length; i++) {
            if (i == skip || i == force) continue;
            if (union(es[i][0], es[i][1])) { w += es[i][2]; cnt++; }
        }
        return cnt == n - 1 ? w : Integer.MAX_VALUE / 2;
    }

    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        int m = edges.length;
        int[][] es = new int[m][4];
        for (int i = 0; i < m; i++) es[i] = new int[]{edges[i][0], edges[i][1], edges[i][2], i};
        Arrays.sort(es, (a, b) -> Integer.compare(a[2], b[2]));
        int base = mstWeight(n, es, -1, -1);
        List<Integer> crit = new ArrayList<>(), pseudo = new ArrayList<>();
        int[] pos = new int[m];
        for (int j = 0; j < m; j++) pos[es[j][3]] = j;
        for (int id = 0; id < m; id++) {
            int j = pos[id];
            if (mstWeight(n, es, j, -1) > base) crit.add(id);
            else if (mstWeight(n, es, -1, j) == base) pseudo.add(id);
        }
        Collections.sort(crit);
        Collections.sort(pseudo);
        return Arrays.asList(crit, pseudo);
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1,1},{1,2,1},{2,3,2},{0,3,2},{0,4,3},{3,4,3},{1,4,6}};
        System.out.println(new CriticalEdges().findCriticalAndPseudoCriticalEdges(5, edges));
        // [[0, 1], [2, 3, 4, 5]]
    }
}

Python.

from typing import List


def find_critical_and_pseudo(n: int, edges: List[List[int]]):
    es = [(u, v, w, i) for i, (u, v, w) in enumerate(edges)]
    es.sort(key=lambda e: e[2])

    def mst_weight(skip=-1, force=-1):
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            parent[ra] = rb
            return True

        w = cnt = 0
        if force != -1:
            u, v, wt, _ = es[force]
            union(u, v)
            w += wt
            cnt += 1
        for i, (u, v, wt, _) in enumerate(es):
            if i == skip or i == force:
                continue
            if union(u, v):
                w += wt
                cnt += 1
        return w if cnt == n - 1 else float("inf")

    base = mst_weight()
    crit, pseudo = [], []
    pos = {e[3]: j for j, e in enumerate(es)}
    for idx in range(len(edges)):
        j = pos[idx]
        if mst_weight(skip=j) > base:
            crit.append(idx)
        elif mst_weight(force=j) == base:
            pseudo.append(idx)
    return [sorted(crit), sorted(pseudo)]


if __name__ == "__main__":
    edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
    print(find_critical_and_pseudo(5, edges))  # [[0, 1], [2, 3, 4, 5]]