hard

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Classify every edge as critical, pseudo-critical, or neither for a minimum spanning tree.

1. Define the problem

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

You are given a weighted, undirected, connected graph of n nodes and an array edges where edgesi = [ai, bi, weighti] represents an edge, identified by its index i in the array. A critical edge is one whose removal increases the minimum spanning tree weight (or disconnects the graph). A pseudo-critical edge is one that isn't critical, but can still be part of some MST of minimum weight. Return [critical, pseudo-critical], both lists of edge indices, in any order within each list. For every edge, run Kruskal's algorithm twice more: once excluding that edge, and once forcing it in before sorting the rest.

Constraints

  • 2 ≤ n ≤ 100
  • 1 ≤ edges.length ≤ min(200, n * (n - 1) / 2)
  • edgesi.length == 3
  • 0 ≤ ai < bi < n
  • 1 ≤ weighti ≤ 1000
  • All pairs (ai, bi) are distinct

Example

Inputn = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output[[0,1],[2,3,4,5]]

Explanation The base MST weighs 7. Removing edge 0 or edge 1 forces a more expensive tree, so both are critical. Edges 2, 3, 4, and 5 can each be forced into a weight-7 tree without being required.

2. Know the words first

In plain terms

Critical edge
An edge that every minimum spanning tree must use — remove it and the cheapest possible tree gets more expensive, or the graph falls apart.
Pseudo-critical edge
An edge that isn't required, but there exists at least one minimum-weight spanning tree that uses it.
3. Visualize the solution

For each edge: rerun Kruskal excluding it, then rerun forcing it in first

For each edge: rerun Kruskal excluding it, then rerun forcing it in first
Statusbase MST: 7

Edge 0 (0–1, weight 1): exclude it and rerun Kruskal — the cheapest tree now costs 8. Critical.

What happens in this step

exclude edge 0 (0–1, w=1); rerun Kruskal on the rest
sorted remaining edges: (1,2,w=1), (2,3,w=2), (0,3,w=2), (0,4,w=3), (3,4,w=3), (1,4,w=6)

accept (1,2,w=1) → weight=1
accept (2,3,w=2) → weight=3, group {1,2,3}
(0,3,w=2): find(0)=0, find(3)=root{1,2,3} → different → accept → weight=5, group {0,1,2,3}
(0,4,w=3): different roots → accept → weight=8, 4 edges used (n-1) → MST complete

8 > base MST (7): removing edge 0 forces a costlier tree, so it is critical.
Step 1 of 5

Steps to visualize

  1. Run Kruskal normally once to find the base minimum spanning tree weight.
  2. For each edge, remove it from consideration and rerun Kruskal — a higher weight (or a disconnected graph) means it is critical.
  3. For every non-critical edge, force it in first, union it, then run Kruskal on the rest — matching the base weight means it is pseudo-critical.
  4. Every other edge is neither: it is never required, and never part of a minimum-weight tree either.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

For each edge: rerun Kruskal excluding it, then rerun forcing it in first
Statusbase MST: 7

Edge 0 (0–1, weight 1): exclude it and rerun Kruskal — the cheapest tree now costs 8. Critical.

What happens in this step

exclude edge 0 (0–1, w=1); rerun Kruskal on the rest
sorted remaining edges: (1,2,w=1), (2,3,w=2), (0,3,w=2), (0,4,w=3), (3,4,w=3), (1,4,w=6)

accept (1,2,w=1) → weight=1
accept (2,3,w=2) → weight=3, group {1,2,3}
(0,3,w=2): find(0)=0, find(3)=root{1,2,3} → different → accept → weight=5, group {0,1,2,3}
(0,4,w=3): different roots → accept → weight=8, 4 edges used (n-1) → MST complete

8 > base MST (7): removing edge 0 forces a costlier tree, so it is critical.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function findCriticalAndPseudoCriticalEdges(n, edges) {
  const indexed = edges.map((e, i) => [e[0], e[1], e[2], i]);

  function mstWeight(skipIndex, forceIndex) {
    const parent = Array.from({ length: n }, (_, i) => i);

    function find(x) {
      while (parent[x] !== x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
      }
      return x;
    }

    function union(a, b) {
      const rootA = find(a);
      const rootB = find(b);
      if (rootA === rootB) return false;
      parent[rootA] = rootB;
      return true;
    }

    let weight = 0;
    let count = 0;

    if (forceIndex !== -1) {
      const [a, b, w] = indexed[forceIndex];
      union(a, b);
      weight += w;
      count++;
    }

    const sorted = [...indexed].sort((x, y) => x[2] - y[2]);
    for (const [a, b, w, idx] of sorted) {
      if (idx === skipIndex || idx === forceIndex) continue;
      if (union(a, b)) {
        weight += w;
        count++;
      }
    }

    if (count !== n - 1) return Infinity;
    return weight;
  }

  const baseWeight = mstWeight(-1, -1);
  const critical = [];
  const pseudoCritical = [];

  for (let i = 0; i < edges.length; i++) {
    if (mstWeight(i, -1) > baseWeight) {
      critical.push(i);
    } else if (mstWeight(-1, i) === baseWeight) {
      pseudoCritical.push(i);
    }
  }

  return [critical, pseudoCritical];
}
Time
O(m² α(n)) — m reruns of Kruskal, each O(m log m)
Space
O(n + m)
6. Test cases

Test cases

InputExpectedCovers
n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]][[0,1],[2,3,4,5]]example from the docstring
n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]][[],[0,1,2,3]]a 4-cycle of equal weights — no edge is required, but every edge could be used
n = 3, edges = [[0,1,1],[1,2,1],[0,2,1]][[],[0,1,2]]a triangle of equal weights — any two edges form a minimum tree
n = 4, edges = [[0,1,5],[2,3,5],[1,2,1]][[0,1,2],[]]already a tree with no redundancy — every edge is required
n = 2, edges = [[0,1,10]][[0],[]]smallest valid input, the only edge is necessarily critical
n = 4, edges = [[0,1,1],[0,2,1],[0,3,1],[1,2,2]][[0,1,2],[]]an extra pricier edge that never belongs to any minimum tree, critical or not

Keep reading