28 · Union-Find & Minimum Spanning Trees

#1489 Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

frequently reported atMeta

the problem

In plain words

Given a connected weighted undirected graph, return two lists of edge indices: critical edges (removing it makes every MST heavier) and pseudo-critical edges (in some MST but not all).

in n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]

out [[0,1],[2,3,4,5]]

Edges 0 and 1 appear in every MST; 2–5 appear in some.

in n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]

out [[],[0,1,2,3]]

Any 3 of the 4 equal edges form an MST.

2 ≤ n ≤ 100
1 ≤ edges.length ≤ min(200, n(n−1)/2)
1 ≤ weight ≤ 1000
The graph is connected

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternMinimum spanning tree (Kruskal / Prim)Union-Find (DSU)

Compute the MST weight W once. An edge is critical if Kruskal without it gives more than W (or can't connect). Otherwise it is pseudo-critical if Kruskal that starts with it still achieves W.

solutions

From brute force to optimal

For each edge run two full Kruskals (skip it / force it), each re-sorting the edges.

W = MST weight.
For each edge i: skip → weight > W? critical.
Else force → weight == W? pseudo-critical.

timeO(E² log E)

2E Kruskal runs, each dominated by an O(E log E) sort.

spaceO(V + E)

One DSU and one index list per run.

javajava.util.*

1class Solution {2    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {3        int best = mst(n, edges, -1, -1);4        List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();5        for (int i = 0; i < edges.length; i++) {6            if (mst(n, edges, i, -1) > best) critical.add(i);         // removing it hurts7            else if (mst(n, edges, -1, i) == best) pseudo.add(i);     // forcing it is free8        }9        return List.of(critical, pseudo);10    }11 12    /** Kruskal from scratch every call: copy, sort, union. Disconnected → MAX_VALUE. */13    private int mst(int n, int[][] edges, int skip, int force) {14        int[] parent = new int[n];15        for (int i = 0; i < n; i++) parent[i] = i;16        int weight = 0, used = 0;17        if (force != -1) {18            parent[find(parent, edges[force][0])] = find(parent, edges[force][1]);19            weight += edges[force][2];20            used++;21        }22        List<Integer> order = new ArrayList<>();23        for (int i = 0; i < edges.length; i++) order.add(i);24        order.sort(Comparator.comparingInt(i -> edges[i][2])); // re-sorted on every call25        for (int i : order) {26            if (i == skip || i == force) continue;27            int ra = find(parent, edges[i][0]), rb = find(parent, edges[i][1]);28            if (ra == rb) continue;29            parent[ra] = rb;30            weight += edges[i][2];31            used++;32        }33        return used == n - 1 ? weight : Integer.MAX_VALUE;34    }35 36    private int find(int[] parent, int x) {37        while (parent[x] != x) x = parent[x] = parent[parent[x]];38        return x;39    }40}

Sort edge indices by weight once and reuse that order for all 2E + 1 Kruskal runs.

Sort indices by weight; W = Kruskal().
Critical: Kruskal(skip = i) > W (disconnected counts as ∞).
Pseudo-critical: not critical and Kruskal(force = i) == W.

timeO(E log E + E²·α(V))

One sort, then 2E + 1 linear passes of near-constant unions. With E ≤ 200 that is tiny.

spaceO(V + E)

The sorted index array plus a fresh DSU per run.

javajava.util.*

1class Solution {2    private int[][] edges;3    private Integer[] order; // edge indices sorted by weight, computed once4 5    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {6        this.edges = edges;7        order = new Integer[edges.length];8        for (int i = 0; i < edges.length; i++) order[i] = i;9        Arrays.sort(order, Comparator.comparingInt(i -> edges[i][2]));10        int best = mst(n, -1, -1);11        List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();12        for (int i = 0; i < edges.length; i++) {13            if (mst(n, i, -1) > best) critical.add(i);14            else if (mst(n, -1, i) == best) pseudo.add(i);15        }16        return List.of(critical, pseudo);17    }18 19    /** Kruskal that can skip one edge or start with one edge forced in. */20    private int mst(int n, int skip, int force) {21        int[] parent = new int[n], size = new int[n];22        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }23        int weight = 0, used = 0;24        if (force != -1) {25            union(parent, size, edges[force][0], edges[force][1]);26            weight += edges[force][2];27            used++;28        }29        for (int i : order) {30            if (i == skip || i == force) continue;31            if (union(parent, size, edges[i][0], edges[i][1])) {32                weight += edges[i][2];33                if (++used == n - 1) break;34            }35        }36        return used == n - 1 ? weight : Integer.MAX_VALUE;37    }38 39    private int find(int[] parent, int x) {40        if (parent[x] != x) parent[x] = find(parent, parent[x]);41        return parent[x];42    }43 44    private boolean union(int[] parent, int[] size, int a, int b) {45        int ra = find(parent, a), rb = find(parent, b);46        if (ra == rb) return false;47        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }48        parent[rb] = ra;49        size[ra] += size[rb];50        return true;51    }52}

in the room

How to say it in the interview

talk track

Define both terms with the skip/force tests before coding — that's the whole solution.
Explain why "force then Kruskal" works: Kruskal is optimal given any starting forest that can be extended, so if the forced edge is in some MST the weight stays W.

traps

Not treating "graph disconnected after skipping" as heavier (it must count as critical).
Testing pseudo-critical for edges already found critical.

what they ask next

Follow-ups

Faster than O(E²)?

Group edges by weight; within each group, edges that join different current components are candidates, and the bridges among them (Tarjan's bridge-finding on the compressed graph) are critical. O(E log E) overall — mention, don't code.

before you submit

Edge cases to test

A single edge between two nodes → critical.
The graph is already a tree → every edge is critical.
All weights equal on a cycle → no critical edges, every edge pseudo-critical.
An edge heavier than every alternative is in no MST → in neither list.

practise next