Find Critical and Pseudo-Critical Edges in MST

Difficulty: Hard Source: NeetCode

Problem

Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi.

A minimum spanning tree (MST) is a subset of the graph’s edges that connects all vertices together without any cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the MST of the given graph.

Critical: removing this edge increases the MST weight (or makes it disconnected)

Pseudo-critical: this edge can appear in some MST, but not all; including it forces some MST of the same weight

Return [criticalEdges, pseudoCriticalEdges] as lists of edge indices.

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.length <= min(200, n*(n-1)/2)

edges[i].length == 3

0 <= ai < bi < n

1 <= weighti <= 1000

All pairs (ai, bi) are distinct

Prerequisites

Before attempting this problem, you should be comfortable with:

Kruskal’s Algorithm — building MST by sorting edges and using Union-Find
Union-Find — tracking connected components efficiently
Brute Force Checking — re-running MST with/without specific edges

1. Brute Force (Naive Check Per Edge)

For each edge, check if it’s critical or pseudo-critical by brute force: build MST without it (critical test) and build MST with it forced in (pseudo-critical test). Compare against the baseline MST weight. This is O(E² * α(n)) which is acceptable given the small constraints (E ≤ 200).

Algorithm

Compute the baseline MST weight using Kruskal’s.
For each edge i:
- Critical test: run Kruskal’s skipping edge i. If resulting weight > baseline (or graph is disconnected), edge i is critical.
- Pseudo-critical test: force edge i into the MST first, then run Kruskal’s on remaining edges. If the total equals baseline, edge i is pseudo-critical.
An edge is pseudo-critical only if it’s not critical.

Solution

def findCriticalAndPseudoCriticalEdges(n, edges):
    # Add original indices before sorting
    indexed_edges = [(w, u, v, i) for i, (u, v, w) in enumerate(edges)]
    indexed_edges.sort()

    def make_uf():
        parent = list(range(n))
        rank = [0] * n

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        return find, union

    def kruskal(skip=-1, force=-1):
        find, union = make_uf()
        weight = 0
        count = 0

        # Force an edge in first
        if force != -1:
            w, u, v, _ = indexed_edges[force]
            union(u, v)
            weight += w
            count += 1

        for idx, (w, u, v, orig) in enumerate(indexed_edges):
            if idx == skip:
                continue
            if union(u, v):
                weight += w
                count += 1

        return weight if count == n - 1 else float('inf')

    baseline = kruskal()
    critical, pseudo_critical = [], []

    for i in range(len(indexed_edges)):
        orig_idx = indexed_edges[i][3]
        # Critical check: skip this edge
        if kruskal(skip=i) > baseline:
            critical.append(orig_idx)
        # Pseudo-critical check: force this edge in
        elif kruskal(force=i) == baseline:
            pseudo_critical.append(orig_idx)

    return [sorted(critical), sorted(pseudo_critical)]


n1 = 5
edges1 = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
print(findCriticalAndPseudoCriticalEdges(n1, edges1))  # [[0,1],[2,3,4,5]]

n2 = 4
edges2 = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
print(findCriticalAndPseudoCriticalEdges(n2, edges2))  # [[],[0,1,2,3]]

Complexity

Time: O(E² * α(n)) — for each edge, two MST runs
Space: O(n + E) — Union-Find and edge list

2. Optimized Approach (Same Complexity, Cleaner Structure)

Intuition

The same approach as above, but structured more cleanly. The key insight is:

An edge is critical if removing it makes the MST weight increase.
An edge is pseudo-critical if including it as a forced edge still gives MST weight equal to baseline.
An edge that is critical cannot be pseudo-critical (it’s already in every MST).

The structure of running Kruskal’s multiple times is hard to avoid for this problem without much more complex algorithms. Given E ≤ 200, the brute force is perfectly fine.

Solution

def findCriticalAndPseudoCriticalEdges_v2(n, edges):
    E = len(edges)
    indexed = sorted(range(E), key=lambda i: edges[i][2])  # sort by weight

    def find(parent, x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(parent, rank, x, y):
        px, py = find(parent, x), find(parent, y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    def mst_weight(skip=-1, force=-1):
        parent = list(range(n))
        rank = [0] * n
        w = 0
        cnt = 0
        if force != -1:
            u, v, wt = edges[force]
            union(parent, rank, u, v)
            w += wt
            cnt += 1
        for i in indexed:
            if i == skip:
                continue
            u, v, wt = edges[i]
            if union(parent, rank, u, v):
                w += wt
                cnt += 1
        return w if cnt == n - 1 else float('inf')

    base = mst_weight()
    crit, pseudo = [], []

    for i in range(E):
        if mst_weight(skip=i) > base:
            crit.append(i)
        elif mst_weight(force=i) == base:
            pseudo.append(i)

    return [crit, pseudo]


n1 = 5
edges1 = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
print(findCriticalAndPseudoCriticalEdges_v2(n1, edges1))  # [[0,1],[2,3,4,5]]

n2 = 4
edges2 = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
print(findCriticalAndPseudoCriticalEdges_v2(n2, edges2))  # [[],[0,1,2,3]]

Complexity

Time: O(E² * α(n)) — same as brute force; unavoidable without heavy machinery
Space: O(n + E)

Common Pitfalls

Sorting edges but losing original indices. You need to sort edges for Kruskal’s, but the output requires original indices. Always track the original index alongside the edge data.

Marking edges as pseudo-critical when they’re actually critical. The pseudo-critical check includes critical edges (forcing a critical edge in still gives baseline weight). Always check critical first, and only check pseudo-critical for non-critical edges.

Forgetting to handle disconnected graphs when skipping edges. If removing an edge disconnects the graph, Kruskal’s won’t be able to form a spanning tree. Return inf in that case (count < n - 1).

Keyboard shortcuts

Note Book