1489. Find Critical and Pseudo-Critical Edges in MST (Hard)

Problem

Given a weighted undirected connected graph with n nodes and edges[i] = [u, v, weight], find:

Critical edges: removing the edge increases the MST weight (or disconnects the graph).
Pseudo-critical edges: the edge appears in at least one MST but not in every MST.

Return [critical_list, pseudo_critical_list] as lists of original edge indices.

Example

n=5, edges: [0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]
Critical: [0,1] (edges with weight 1)
Pseudo-critical: [2,3,4,5] (any of the weight-2 or weight-3 edges can be swapped)

LeetCode 1489 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Background: Kruskal’s algorithm and Union-Find

Kruskal builds an MST by sorting edges by weight and greedily adding each edge if it doesn’t form a cycle. Cycle detection uses Union-Find with path compression.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))      # each node is its own root
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                  # already same component, cycle!
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True                       # merged successfully

class UnionFind {
    parent: number[];
    rank: number[];
    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x: number): number {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x: number, y: number): boolean {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;      // already same component, cycle!
        if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];
        this.parent[ry] = rx;
        if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;
        return true;                      // merged successfully
    }
}

// See 1489-critical-and-pseudo-critical-edges-approach2.go for the Go UnionFind type.
type UF1489 struct { parent, rank []int }
func newUF1489(n int) *UF1489 {
    uf := &UF1489{parent: make([]int, n), rank: make([]int, n)}
    for i := range uf.parent { uf.parent[i] = i }
    return uf
}
func (uf *UF1489) find(x int) int {
    for uf.parent[x] != x { uf.parent[x] = uf.parent[uf.parent[x]]; x = uf.parent[x] }
    return x
}
func (uf *UF1489) union(x, y int) bool {
    rx, ry := uf.find(x), uf.find(y)
    if rx == ry { return false }           // already same component, cycle!
    if uf.rank[rx] < uf.rank[ry] { rx, ry = ry, rx }
    uf.parent[ry] = rx
    if uf.rank[rx] == uf.rank[ry] { uf.rank[rx]++ }
    return true                            // merged successfully
}

Approach: Brute force per-edge classification

For each edge e (indexed in sorted order), run two modified Kruskal passes:

Critical test: build MST excluding e. If MST weight increases or graph disconnects, e is critical.
Pseudo-critical test: build MST forcing e in first. If the resulting MST weight equals the base MST weight, e is pseudo-critical.

def find_critical_and_pseudo_critical_edges(n, edges):
    # attach original indices before sorting
    indexed = [(w, u, v, i) for i, (u, v, w) in enumerate(edges)]  # L1: O(E)
    indexed.sort()                                                   # L2: O(E log E)

    def kruskal(n, edges, skip=-1, force=-1):                        # L3: helper
        uf = UnionFind(n)
        weight = 0
        count = 0
        if force != -1:                                              # L4: force edge in first
            w, u, v, _ = edges[force]
            uf.union(u, v)
            weight += w
            count += 1
        for idx, (w, u, v, orig) in enumerate(edges):               # L5: O(E) Kruskal
            if idx == skip:                                          # L6: skip this edge
                continue
            if uf.union(u, v):                                       # L7: no cycle
                weight += w
                count += 1
        if count < n - 1:                                            # L8: disconnected
            return float('inf')
        return weight

    base = kruskal(n, indexed)                                       # L9: O(E alpha(V))
    critical = []
    pseudo = []

    for i in range(len(indexed)):                                    # L10: O(E) outer loop
        # critical test: exclude edge i
        if kruskal(n, indexed, skip=i) > base:                      # L11: O(E alpha(V))
            critical.append(indexed[i][3])
        # pseudo-critical test: force edge i
        elif kruskal(n, indexed, force=i) == base:                  # L12: O(E alpha(V))
            pseudo.append(indexed[i][3])

    critical.sort()                                                  # L13: O(E log E)
    pseudo.sort()
    return [critical, pseudo]

function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
    // attach original indices before sorting
    const indexed: [number, number, number, number][] = edges.map(([u, v, w], i) => [w, u, v, i]);
    indexed.sort((a, b) => a[0] - b[0]);                            // L2: O(E log E)

    function kruskal(skip = -1, force = -1): number {               // L3: helper
        const uf = new UnionFind(n);
        let weight = 0, count = 0;
        if (force !== -1) {                                         // L4: force edge in first
            const [w, u, v] = indexed[force];
            uf.union(u, v);
            weight += w;
            count++;
        }
        for (let idx = 0; idx < indexed.length; idx++) {           // L5: O(E) Kruskal
            if (idx === skip) continue;                             // L6: skip this edge
            const [w, u, v] = indexed[idx];
            if (uf.union(u, v)) { weight += w; count++; }          // L7: no cycle
        }
        return count < n - 1 ? Infinity : weight;                  // L8: disconnected check
    }

    const base = kruskal();                                         // L9: O(E alpha(V))
    const critical: number[] = [], pseudo: number[] = [];

    for (let i = 0; i < indexed.length; i++) {                     // L10: O(E) outer loop
        if (kruskal(i) > base) critical.push(indexed[i][3]);       // L11: critical test
        else if (kruskal(-1, i) === base) pseudo.push(indexed[i][3]);  // L12: pseudo-critical test
    }
    critical.sort((a, b) => a - b);                                // L13: O(E log E)
    pseudo.sort((a, b) => a - b);
    return [critical, pseudo];
}

// See 1489-critical-and-pseudo-critical-edges-approach2.go for the full runnable program.
func findCriticalAndPseudoCriticalEdges(n int, edges [][]int) [][]int {
    type IndexedEdge struct{ w, u, v, orig int }
    indexed := make([]IndexedEdge, len(edges))
    for i, e := range edges { indexed[i] = IndexedEdge{e[2], e[0], e[1], i} }  // L1: O(E)
    sort.Slice(indexed, func(i, j int) bool { return indexed[i].w < indexed[j].w })  // L2: O(E log E)

    kruskal := func(skip, force int) int {                         // L3: helper
        uf := newUF1489(n)
        weight, count := 0, 0
        if force != -1 {                                           // L4: force edge in first
            e := indexed[force]; uf.union(e.u, e.v); weight += e.w; count++
        }
        for idx, e := range indexed {                              // L5: O(E) Kruskal
            if idx == skip { continue }                            // L6: skip this edge
            if uf.union(e.u, e.v) { weight += e.w; count++ }      // L7: no cycle
        }
        if count < n-1 { return 1<<31 - 1 }                       // L8: disconnected
        return weight
    }

    base := kruskal(-1, -1)                                        // L9: O(E alpha(V))
    var critical, pseudo []int
    for i, e := range indexed {                                    // L10: O(E) outer loop
        if kruskal(i, -1) > base { critical = append(critical, e.orig) }       // L11
        else if kruskal(-1, i) == base { pseudo = append(pseudo, e.orig) }     // L12
    }
    sort.Ints(critical); sort.Ints(pseudo)                         // L13: O(E log E)
    if critical == nil { critical = []int{} }
    if pseudo == nil { pseudo = []int{} }
    return [][]int{critical, pseudo}
}

Where the time goes, line by line

Variables: V = n (nodes), E = number of edges, alpha = inverse Ackermann (near-constant).

Line	Per-call cost	Times executed	Contribution
L1-L2 (index + sort)	$O(E log E)$	1	$O(E log E)$
L9 (base Kruskal)	$O(E alpha(V)$ )	1	$O(E alpha(V)$ )
L10 (outer loop)	$O(1)$	E	$O(E)$
L11/L12 (Kruskal calls)	$O(E alpha(V)$ )	2E	$O(E^2 alpha(V)$ ) ← dominates
L13 (sort results)	$O(E log E)$	1	$O(E log E)$

For each of E edges, we run two $O(E alpha(V)$ ) Kruskal passes, giving $O(E^2 alpha(V)$ ) total. Since alpha(V) is effectively constant (< 5 for all practical inputs), this is essentially $O(E^2)$ .

Complexity

Time: $O(E^2 alpha(V)$ ), driven by L11/L12 (two Kruskal passes per edge).
Space: $O(V + E)$ for the Union-Find and edge list.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func findCriticalAndPseudoCriticalEdges(_ n: Int, _ edges: [[Int]]) -> [[Int]] {
        let ordered = edges.enumerated().map { [$0.element[0], $0.element[1], $0.element[2], $0.offset] }.sorted { $0[2] < $1[2] }
        func mst(skipping skipped: Int?, forcing forced: Int?) -> Int {
            var parent = Array(0..<n), rank = Array(repeating: 0, count: n), total = 0, used = 0
            func find(_ value: Int) -> Int { var node = value; while parent[node] != node { node = parent[node] }; return node }
            func unite(_ left: Int, _ right: Int) -> Bool {
                var a = find(left), b = find(right); if a == b { return false }
                if rank[a] < rank[b] { swap(&a, &b) }; parent[b] = a; if rank[a] == rank[b] { rank[a] += 1 }; return true
            }
            if let forced { let edge = ordered[forced]; if unite(edge[0], edge[1]) { total += edge[2]; used += 1 } }
            for index in ordered.indices where index != skipped && index != forced {
                let edge = ordered[index]; if unite(edge[0], edge[1]) { total += edge[2]; used += 1 }
            }
            return used == n - 1 ? total : Int.max / 4
        }
        let baseline = mst(skipping: nil, forcing: nil); var critical: [Int] = [], pseudo: [Int] = []
        for index in ordered.indices {
            if mst(skipping: index, forcing: nil) > baseline { critical.append(ordered[index][3]) }
            else if mst(skipping: nil, forcing: index) == baseline { pseudo.append(ordered[index][3]) }
        }
        return [critical.sorted(), pseudo.sorted()]
    }
}

Why not $O(E log E)$ for the whole problem?

We run Kruskal $O(E)$ times (once per edge, twice per test). Each Kruskal is $O(E alpha(V)$ ). There is no known algorithm better than $O(E^2)$ for this problem in the general case, though matroid intersection theory can improve it in practice.

Classifying edge types visually

Sorted edges: [w=1, e0], [w=1, e1], [w=2, e2], [w=2, e3], [w=3, e4], [w=3, e5]

Base MST picks e0, e1, then one of {e2, e3}, then one of {e4, e5}.
Weight = 1+1+2+3 = 7.

Test e0 (exclude): remaining edges can't achieve weight 7 -> CRITICAL.
Test e2 (exclude): e3 steps in with same weight -> MST weight still 7.
  Force e2 (include): MST weight = 7 -> PSEUDO-CRITICAL.

Summary

Step	Operation	Purpose
Sort edges	$O(E log E)$	Kruskal prerequisite
Base MST	$O(E alpha(V)$ )	Reference weight
Critical test	Kruskal excluding edge	Weight increases?
Pseudo-critical test	Kruskal forcing edge	Weight stays same?

The pattern: establish a baseline, then test each candidate by modifying the baseline construction. This same “remove one, rebuild” pattern appears in sensitivity analysis for many combinatorial optimization problems.

Test cases

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        return True

def find_critical_and_pseudo_critical_edges(n, edges):
    indexed = [(w, u, v, i) for i, (u, v, w) in enumerate(edges)]
    indexed.sort()

    def kruskal(skip=-1, force=-1):
        uf = UnionFind(n)
        weight = 0
        count = 0
        if force != -1:
            w, u, v, _ = indexed[force]
            uf.union(u, v)
            weight += w
            count += 1
        for idx, (w, u, v, orig) in enumerate(indexed):
            if idx == skip: continue
            if uf.union(u, v):
                weight += w
                count += 1
        return float('inf') if count < n - 1 else weight

    base = kruskal()
    critical, pseudo = [], []
    for i in range(len(indexed)):
        if kruskal(skip=i) > base:
            critical.append(indexed[i][3])
        elif kruskal(force=i) == base:
            pseudo.append(indexed[i][3])
    critical.sort()
    pseudo.sort()
    return [critical, pseudo]

def _run_tests():
    assert find_critical_and_pseudo_critical_edges(5, [[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]]
    assert find_critical_and_pseudo_critical_edges(4, [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]) == [[],[0,1,2,3]]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class UnionFind {
    parent: number[];
    rank: number[];
    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x: number): number {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x: number, y: number): boolean {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];
        this.parent[ry] = rx;
        if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;
        return true;
    }
}

function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
    const indexed: [number, number, number, number][] = edges.map(([u, v, w], i) => [w, u, v, i]);
    indexed.sort((a, b) => a[0] - b[0]);

    function kruskal(skip = -1, force = -1): number {
        const uf = new UnionFind(n);
        let weight = 0, count = 0;
        if (force !== -1) {
            const [w, u, v] = indexed[force];
            uf.union(u, v); weight += w; count++;
        }
        for (let idx = 0; idx < indexed.length; idx++) {
            if (idx === skip) continue;
            const [w, u, v] = indexed[idx];
            if (uf.union(u, v)) { weight += w; count++; }
        }
        return count < n - 1 ? Infinity : weight;
    }

    const base = kruskal();
    const critical: number[] = [], pseudo: number[] = [];
    for (let i = 0; i < indexed.length; i++) {
        if (kruskal(i) > base) critical.push(indexed[i][3]);
        else if (kruskal(-1, i) === base) pseudo.push(indexed[i][3]);
    }
    critical.sort((a, b) => a - b);
    pseudo.sort((a, b) => a - b);
    return [critical, pseudo];
}

console.assert(JSON.stringify(findCriticalAndPseudoCriticalEdges(5, [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]])) === JSON.stringify([[0,1],[2,3,4,5]]));
console.assert(JSON.stringify(findCriticalAndPseudoCriticalEdges(4, [[0,1,1],[1,2,1],[2,3,1],[0,3,1]])) === JSON.stringify([[],[0,1,2,3]]));
console.log("all tests pass");

Critical Connections in a Network, bridge-finding via Tarjan’s algorithm
Network Delay Time, weighted graph shortest paths
Min Cost to Connect All Points, Kruskal/Prim for MST

Union Find, the component tracking structure for connectivity as edges are processed.
Sorting as Preprocessing, the order first tactic that exposes adjacency, sweep boundaries, and duplicate control.

1489. Find Critical and Pseudo-Critical Edges in MST (Hard)

Problem

Try it yourself

Background: Kruskal’s algorithm and Union-Find

Approach: Brute force per-edge classification

Why not O(ElogE)O(E log E)O(ElogE) for the whole problem?

Classifying edge types visually

Summary

Test cases

Related topics

Related concepts

Why not $O(E log E)$ for the whole problem?