Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

NeetCode: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree · LeetCode: 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree · Difficulty: Hard

Given a connected, undirected, weighted graph with n vertices and edges[i] = [a, b, weight], find its minimum spanning tree (MST) weight. An edge is critical if deleting it increases the MST weight (or disconnects the graph). An edge is pseudo-critical if it appears in some MST but not in all of them. Return the indices of both kinds, each list sorted.

Example

Text

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: critical = [0, 1], pseudo-critical = [2, 3, 4, 5]
Input:  n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: critical = [], pseudo-critical = [0, 1, 2, 3]

Brute force: recompute the MST for every edge

Kruskal's algorithm sorts the edges by weight and adds an edge whenever it joins two different components (tracked with union-find). Let best be the weight of the plain MST. For each edge i:

Exclude it and rebuild the MST. If the graph becomes disconnected or the weight is larger than best, the edge is critical.
Otherwise force it in (union its endpoints first, then run Kruskal). If the weight still equals best, some MST uses it, so it is pseudo-critical.

The result is a list of two lists: the critical indices, then the pseudo-critical ones. This runs Kruskal up to 2E times. It is correct and fast enough for n <= 100, E <= 200, but does not scale to larger graphs.

mst returns the MST weight, or -1 when the edges used cannot connect the graph (weights are positive, so -1 never collides with a real weight). skip and force are edge indices, or -1 for "none". The sort of indices uses Integer.compare on the weights, so it cannot overflow.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private static class Dsu {
        final int[] parent;

        Dsu(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            parent[ra] = rb;
            return true;
        }
    }

    // MST weight using edges in sorted `order`, optionally skipping one edge
    // or forcing one in first. Returns -1 when the graph is not connected.
    private int mst(int n, int[][] edges, Integer[] order, int skip, int force) {
        Dsu dsu = new Dsu(n);
        int total = 0, used = 0;
        if (force != -1) {
            dsu.union(edges[force][0], edges[force][1]);
            total += edges[force][2];
            used++;
        }
        for (int i : order) {
            if (i == skip) continue;
            if (dsu.union(edges[i][0], edges[i][1])) {
                total += edges[i][2];
                used++;
            }
        }
        return used == n - 1 ? total : -1;
    }

    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        Integer[] order = new Integer[edges.length];
        for (int i = 0; i < order.length; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(edges[a][2], edges[b][2]));
        int best = mst(n, edges, order, -1, -1);
        List<Integer> critical = new ArrayList<>();
        List<Integer> pseudo = new ArrayList<>();
        for (int i = 0; i < edges.length; i++) {
            int without = mst(n, edges, order, i, -1);
            if (without == best) {
                // Not critical. It is pseudo-critical if some MST can include it.
                if (mst(n, edges, order, -1, i) == best) pseudo.add(i);
            } else {
                critical.add(i);
            }
        }
        return List.of(critical, pseudo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] e1 = {{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2}, {0, 4, 3}, {3, 4, 3}, {1, 4, 6}};
        System.out.println(s.findCriticalAndPseudoCriticalEdges(5, e1));
        int[][] e2 = {{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {0, 3, 1}};
        System.out.println(s.findCriticalAndPseudoCriticalEdges(4, e2));
        // A path: every edge is critical.
        int[][] e3 = {{0, 1, 5}, {1, 2, 7}};
        System.out.println(s.findCriticalAndPseudoCriticalEdges(3, e3));
    }
}

Output

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

Time: O(E^2 · α(n)) after one O(E log E) sort. Space: O(n + E).

Optimal: Kruskal by weight group, then bridges

Whether an edge is critical depends only on the edges of its own weight. Process the edges in groups of equal weight. Before a group, the union-find holds the components built from all lighter edges. Inside the group:

An edge whose endpoints are already in the same component can never be in an MST (a cheaper path connects them). It is neither critical nor pseudo-critical.
The remaining edges form a small multigraph whose vertices are the component roots. An edge that is a bridge of this multigraph is the only way to join its two sides at this weight, so every MST uses it: critical. Every other such edge lies on a cycle of equal-weight edges, so it can be swapped in or out: pseudo-critical.

After classifying a group, union all its edges and move on to the next weight. Bridges are found with one DFS using discovery times and low-links. Parallel edges are handled by skipping the edge id used to arrive at a vertex, not the parent vertex.

Trace for the first example. Weight 1: edges 0 (0-1) and 1 (1-2) join separate components; the multigraph is a path, so both are bridges: critical. Union them. Weight 2: edge 2 (2-3) and edge 3 (0-3) connect component {0,1,2} to vertex 3, giving two parallel edges between the same pair of roots, so neither is a bridge: both pseudo-critical. After the union, weight 3: edges 4 (0-4) and 5 (3-4) are also parallel between {0,1,2,3} and vertex 4: pseudo-critical. Weight 6: edge 6 (1-4) has both ends in one component, so it is in no MST. Result: critical [0, 1], pseudo-critical [2, 3, 4, 5].

The bridge search is a recursive DFS, which is fine for the problem's n <= 100. The DFS state (adjacency lists, discovery times, low-links) lives in fields of Solution, and the pieces are reset per group.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private static class Dsu {
        final int[] parent;

        Dsu(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        void union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra != rb) parent[ra] = rb;
        }
    }

    // Bridge finder over the multigraph of component roots for one weight group.
    private List<List<int[]>> adj; // per component: {neighbour component, edge id}
    private int[] disc;            // discovery time, 0 = unvisited
    private int[] low;             // earliest discovery time reachable from the subtree
    private int timer;
    private boolean[] isBridge;

    private void dfs(int u, int parentEdge) {
        timer++;
        disc[u] = timer;
        low[u] = timer;
        for (int[] edge : adj.get(u)) {
            int v = edge[0], id = edge[1];
            if (id == parentEdge) continue; // skip the edge we arrived by, not the parent vertex
            if (disc[v] == 0) {
                dfs(v, id);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) isBridge[id] = true;
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }

    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        Integer[] order = new Integer[edges.length];
        for (int i = 0; i < order.length; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(edges[a][2], edges[b][2]));

        Dsu dsu = new Dsu(n);
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        disc = new int[n];
        low = new int[n];
        timer = 0;
        isBridge = new boolean[edges.length];
        boolean[] inSomeMst = new boolean[edges.length];

        int start = 0;
        while (start < order.length) {
            int w = edges[order[start]][2];
            int end = start;
            while (end < order.length && edges[order[end]][2] == w) end++;

            // Build the multigraph over component roots; edges inside a component are skipped.
            List<Integer> touched = new ArrayList<>();
            for (int k = start; k < end; k++) {
                int id = order[k];
                int a = dsu.find(edges[id][0]);
                int b = dsu.find(edges[id][1]);
                if (a != b) {
                    adj.get(a).add(new int[] {b, id});
                    adj.get(b).add(new int[] {a, id});
                    touched.add(a);
                    touched.add(b);
                    inSomeMst[id] = true;
                }
            }
            for (int s : touched) {
                if (disc[s] == 0) dfs(s, -1);
            }
            // Reset only the vertices used by this group.
            for (int s : touched) {
                adj.get(s).clear();
                disc[s] = 0;
                low[s] = 0;
            }
            for (int k = start; k < end; k++) {
                dsu.union(edges[order[k]][0], edges[order[k]][1]);
            }
            start = end;
        }

        List<Integer> critical = new ArrayList<>();
        List<Integer> pseudo = new ArrayList<>();
        for (int i = 0; i < edges.length; i++) {
            if (isBridge[i]) critical.add(i);
            else if (inSomeMst[i]) pseudo.add(i);
        }
        return List.of(critical, pseudo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] e1 = {{0, 1, 1}, {1, 2, 1}, {2, 3, 2}, {0, 3, 2}, {0, 4, 3}, {3, 4, 3}, {1, 4, 6}};
        System.out.println(s.findCriticalAndPseudoCriticalEdges(5, e1));
        int[][] e2 = {{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {0, 3, 1}};
        System.out.println(s.findCriticalAndPseudoCriticalEdges(4, e2));
        // A path: every edge is critical.
        int[][] e3 = {{0, 1, 5}, {1, 2, 7}};
        System.out.println(s.findCriticalAndPseudoCriticalEdges(3, e3));
    }
}

Output

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

Time: O(E log E) for the sort, plus near-linear work for the groups (each edge is visited a constant number of times by the DFS and union-find), so O(E log E) overall. Space: O(n + E).

Edge cases

Every edge has the same weight: one group, and edges on cycles are all pseudo-critical.
A tree (path): every edge is a bridge, so all are critical.
An edge whose endpoints are already connected by lighter edges is in no MST and appears in neither list.
Parallel edges: bridge detection skips by edge id, so two parallel edges are never bridges.

How to explain it in an interview

Brute force: compute the MST weight; for each edge, exclude it (weight rises or graph disconnects means critical), otherwise force it in (same weight means pseudo-critical). This is O(E^2 * alpha(n)).
Sort edges by weight and process equal-weight groups with Kruskal's union-find.
Within a group, contract the existing components into vertices; edges inside one component are useless.
A bridge of the contracted multigraph is required for connectivity at this weight, so it is critical.
Non-bridge edges lie on an equal-weight cycle and can be swapped, so they are pseudo-critical.
Bridges come from one DFS with discovery times and low-links; total time is O(E log E).