Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree — Hard Problem & Solution

Problem statement

A connected, weighted, undirected graph has n vertices numbered 0 to n - 1. Edge i is edges[i] = [ai, bi, weighti]. A minimum spanning tree (MST) is a subset of the edges that connects all vertices without cycles and has the smallest possible total weight.

• An edge is critical if deleting it from the graph would make every remaining spanning tree heavier (it belongs to every MST).
• An edge is pseudo-critical if it belongs to some MSTs but not to all of them.

Return [critical, pseudo]: the indices of the critical edges and of the pseudo-critical edges, each list in ascending order.

Example 1

Input: n = 4, edges = [[0,1,1],[1,2,2],[2,3,1],[0,3,3],[1,3,2]]
Output: [[0,2],[1,4]]
Explanation: Every MST weighs 4 and uses edges 0 and 2 plus one of edges 1 and 4; edge 3 is never used.

Example 2

Input: n = 3, edges = [[0,1,5],[1,2,5],[0,2,5]]
Output: [[],[0,1,2]]
Explanation: Any two of the three equal edges form an MST.

Example 3

Input: n = 2, edges = [[0,1,7]]
Output: [[0],[]]

Constraints

• 2 <= n <= 100
• 1 <= edges.length <= min(200, n * (n - 1) / 2)
• edges[i].length == 3
• 0 <= ai < bi < n
• 1 <= weighti <= 1000
• all pairs (ai, bi) are distinct
• the graph is connected

How to solve Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Use Kruskal as a subroutine that can skip one edge or force one edge in, and compare its result with the true MST weight.

Approach

1. Sort edge indices by weight. mst(skip, force) runs Kruskal with a fresh union-find: it first adds the forced edge (if any), then scans the sorted edges, ignoring skip; it returns the total weight, or ∞ if fewer than n − 1 edges were taken.
2. Let base = mst(none, none).
3. For every edge i: if mst(skip = i) > base, edge i is critical.
4. Otherwise, if mst(force = i) == base, edge i is pseudo-critical.
5. Return both lists, collected in increasing index order.

Why it works

If some MST avoids edge i, Kruskal without i finds a tree of weight base; if none does, every spanning tree without i is heavier — that is exactly criticality. For a non-critical edge, forcing it in and completing greedily yields the cheapest spanning tree that contains i (the cut/cycle properties make greedy completion optimal); it weighs base exactly when some MST contains i.

Complexity

• Time — O(m² · α(n) + m log m)
• Space — O(n + m)

Pitfalls

• Removing an edge can disconnect the graph — treat that as an infinitely heavy tree, which makes the edge critical.
• Check criticality first: a critical edge also passes the forced-in test but must not be listed as pseudo-critical.
• Indices refer to the original order of edges, not the sorted order.

Reference solution

Python

from typing import List

def findCriticalAndPseudoCriticalEdges(n: int, edges: List[List[int]]) -> List[List[int]]:
    m = len(edges)
    order = sorted(range(m), key=lambda i: edges[i][2])
    INF = 10 ** 9

    def mst(skip, force):
        root = list(range(n))

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

        total = 0
        used = 0
        if force >= 0:
            a, b, w = edges[force]
            root[find(a)] = find(b)
            total += w
            used += 1
        for i in order:
            if i == skip:
                continue
            a, b, w = edges[i]
            ra, rb = find(a), find(b)
            if ra != rb:
                root[ra] = rb
                total += w
                used += 1
        return total if used == n - 1 else INF

    base = mst(-1, -1)
    critical, pseudo = [], []
    for i in range(m):
        if mst(i, -1) > base:
            critical.append(i)
        elif mst(-1, i) == base:
            pseudo.append(i)
    return [critical, pseudo]

JavaScript

var findCriticalAndPseudoCriticalEdges = function(n, edges) {
    var m = edges.length;
    var order = [];
    for (var i = 0; i < m; i++) order.push(i);
    order.sort(function(p, q) { return edges[p][2] - edges[q][2]; });
    var INF = 1000000000;
    var mst = function(skip, force) {
        var root = [];
        for (var k = 0; k < n; k++) root.push(k);
        var find = function(x) {
            while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
            return x;
        };
        var total = 0, used = 0;
        if (force >= 0) {
            root[find(edges[force][0])] = find(edges[force][1]);
            total += edges[force][2];
            used++;
        }
        for (var t = 0; t < m; t++) {
            var e = order[t];
            if (e === skip) continue;
            var ra = find(edges[e][0]), rb = find(edges[e][1]);
            if (ra !== rb) { root[ra] = rb; total += edges[e][2]; used++; }
        }
        return used === n - 1 ? total : INF;
    };
    var base = mst(-1, -1);
    var critical = [], pseudo = [];
    for (var j = 0; j < m; j++) {
        if (mst(j, -1) > base) critical.push(j);
        else if (mst(-1, j) === base) pseudo.push(j);
    }
    return [critical, pseudo];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Minimum Cost to Make at Least One Valid Path in a Grid Hard
• Remove Max Number of Edges to Keep Graph Fully Traversable Hard
• Minimize Malware Spread Hard
• Sum of Distances in Tree Hard
• Shortest Cycle in a Graph Hard
• Divide Nodes Into the Maximum Number of Groups Hard