Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Hard
1547.

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree is a hard coding problem on sorting, graph and union find, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var findCriticalAndPseudoCriticalEdges = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree is a hard coding problem on sorting, graph and union find, asked in Amazon and Google interviews.

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

Hints for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

  1. Hint 1

    First compute the MST weight with Kruskal's algorithm.

  2. Hint 2

    An edge is critical exactly when leaving it out makes the best spanning tree heavier (or disconnects the graph).

  3. Hint 3

    An edge that is not critical is pseudo-critical exactly when forcing it into the tree first still allows a spanning tree of the MST weight. Rerun Kruskal for each edge, twice.

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]

Java

public static int[][] findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
    int m = edges.length;
    Integer[] boxed = new Integer[m];
    for (int i = 0; i < m; i++) boxed[i] = i;
    Arrays.sort(boxed, (p, q) -> Integer.compare(edges[p][2], edges[q][2]));
    int[] order = new int[m];
    for (int i = 0; i < m; i++) order[i] = boxed[i];
    int base = cpMst(n, edges, order, -1, -1);
    List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
    for (int i = 0; i < m; i++) {
        if (cpMst(n, edges, order, i, -1) > base) critical.add(i);
        else if (cpMst(n, edges, order, -1, i) == base) pseudo.add(i);
    }
    int[][] res = new int[2][];
    res[0] = new int[critical.size()];
    for (int k = 0; k < res[0].length; k++) res[0][k] = critical.get(k);
    res[1] = new int[pseudo.size()];
    for (int k = 0; k < res[1].length; k++) res[1][k] = pseudo.get(k);
    return res;
}

static int cpFind(int[] root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

static int cpMst(int n, int[][] edges, int[] order, int skip, int force) {
    int[] root = new int[n];
    for (int k = 0; k < n; k++) root[k] = k;
    int total = 0, used = 0;
    if (force >= 0) {
        root[cpFind(root, edges[force][0])] = cpFind(root, edges[force][1]);
        total += edges[force][2];
        used++;
    }
    for (int e : order) {
        if (e == skip) continue;
        int ra = cpFind(root, edges[e][0]), rb = cpFind(root, edges[e][1]);
        if (ra != rb) { root[ra] = rb; total += edges[e][2]; used++; }
    }
    return used == n - 1 ? total : Integer.MAX_VALUE;
}

C++

static int cpFind(vector<int>& root, int x) {
    while (root[x] != x) { root[x] = root[root[x]]; x = root[x]; }
    return x;
}

static int cpMst(int n, vector<vector<int>>& edges, vector<int>& order, int skip, int force) {
    vector<int> root(n);
    for (int k = 0; k < n; k++) root[k] = k;
    int total = 0, used = 0;
    if (force >= 0) {
        root[cpFind(root, edges[force][0])] = cpFind(root, edges[force][1]);
        total += edges[force][2];
        used++;
    }
    for (int e : order) {
        if (e == skip) continue;
        int ra = cpFind(root, edges[e][0]), rb = cpFind(root, edges[e][1]);
        if (ra != rb) { root[ra] = rb; total += edges[e][2]; used++; }
    }
    return used == n - 1 ? total : INT_MAX;
}

vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
    int m = edges.size();
    vector<int> order(m);
    for (int i = 0; i < m; i++) order[i] = i;
    stable_sort(order.begin(), order.end(), [&](int p, int q) { return edges[p][2] < edges[q][2]; });
    int base = cpMst(n, edges, order, -1, -1);
    vector<vector<int>> res(2);
    for (int i = 0; i < m; i++) {
        if (cpMst(n, edges, order, i, -1) > base) res[0].push_back(i);
        else if (cpMst(n, edges, order, -1, i) == base) res[1].push_back(i);
    }
    return res;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 274 sorting problems · the whole catalogue

Learn the technique: Sorting Algorithms · Graph Data Structure