Problem 27.4 · Minimum Spanning TreesHard

Find Critical and Pseudo-Critical Edges in MST

What it teaches: Test an edge's role by rebuilding the MST without it and with it forced in.

Practise it on judges as “Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree”.

The problem

An edge is critical if removing it increases the MST weight (or disconnects the graph). It's pseudo-critical if it appears in some MST but not all. Return [critical indices, pseudo-critical indices], each in increasing order.

Example 1

Input: n = 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]]

Constraints

2 ≤ n ≤ 100
1 ≤ edges ≤ 200

Pattern clues in the wording

→ Which edges every / some MST uses
→ Small input

These clues point to Minimum Spanning Tree: Connect all nodes with the cheapest total edges: sort edges and add each one that doesn't form a cycle (Kruskal).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	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]]
2	n = 4 edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]	[[],[0,1,2,3]]

From slow to fast

Approaches

1. Kruskal with skip and force · O(E² α(V))

Kruskal with skip and force

Time O(E² α(V)) Space O(V + E)

Sort edge indices by weight once. mst(skip, force) runs Kruskal, optionally starting with a forced edge and ignoring a skipped one. Compare with the base weight for each edge.

Approach 1

import java.util.*;

class Solution {
    private int n;
    private int[][] edges;
    private Integer[] order;

    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        this.n = n;
        this.edges = edges;
        order = new Integer[edges.length];
        for (int i = 0; i < edges.length; i++) order[i] = i;
        Arrays.sort(order, Comparator.comparingInt(i -> edges[i][2]));
        int base = mst(-1, -1);
        List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
        for (int i = 0; i < edges.length; i++) {
            if (mst(i, -1) > base) critical.add(i);
            else if (mst(-1, i) == base) pseudo.add(i);
        }
        return List.of(critical, pseudo);
    }

    /** MST weight skipping one edge and/or forcing one in first; MAX_VALUE if disconnected. */
    private int mst(int skip, int force) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int total = 0, used = 0;
        if (force != -1) {
            parent[find(parent, edges[force][0])] = find(parent, edges[force][1]);
            total += edges[force][2];
            used++;
        }
        for (int i : order) {
            if (i == skip) continue;
            int a = find(parent, edges[i][0]), b = find(parent, edges[i][1]);
            if (a == b) continue;
            parent[a] = b;
            total += edges[i][2];
            used++;
        }
        return used == n - 1 ? total : Integer.MAX_VALUE;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: Small limits make 2E Kruskal runs fine.

Before you submit

Edge cases and common mistakes

Test these inputs

All weights equal (every edge pseudo-critical in a cycle)
A bridge (always critical)

Mistakes people make

Calling an edge pseudo-critical when it's actually critical (check critical first).

Interview

Follow-up questions

Is there a faster method?

Command Palette

The problem

Approaches

Kruskal with skip and force

Edge cases and common mistakes

Follow-up questions