Find Critical and Pseudo-Critical Edges in MST: Union-Find Classification

LeetCode Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (problem 1489) gives you n nodes and a list of weighted edges. You need to find the minimum spanning tree (MST) and classify every edge into one of three categories. A critical edge appears in every possible MST. A pseudo-critical edge appears in at least one MST but not necessarily all of them. All other edges appear in no MST at all. Return two lists: the indices of the critical edges and the indices of the pseudo-critical edges.

Why this problem matters

MST problems show up frequently in interviews, but they usually stop at "find the MST." This problem goes further by asking you to reason about the structure of the MST itself. Which edges are essential? Which are interchangeable? Answering these questions requires a deeper understanding of how Kruskal's algorithm works and what happens when you perturb the edge set.

The classification technique you learn here applies beyond this specific problem. In network design, identifying critical links (whose failure disconnects the network or raises cost) is a fundamental task. The "remove and rebuild" and "force and rebuild" testing patterns are reusable tools you can apply to any optimization problem where you need to understand sensitivity to individual choices.

This problem also gives you serious practice with Union-Find. You will run Kruskal's algorithm multiple times (once for the baseline, then once per edge for testing), so your Union-Find implementation needs to be clean and efficient. The repetition cements the data structure in your muscle memory.

The key insight

You can classify each edge with two experiments. First, remove the edge and compute the MST of the remaining graph. If the MST cost goes up (or the graph becomes disconnected), the edge is critical. It must be in every MST because no alternative can replace it at the same cost.

Second, for edges that are not critical, force-include the edge (union its endpoints before running Kruskal's) and compute the MST. If the total cost equals the base MST cost, the edge is pseudo-critical. It can participate in some optimal MST, even though other edges could substitute for it. If forcing the edge raises the cost, it belongs to no MST at all.

The key realization is that these two tests are both necessary and sufficient. Removal tests whether the edge is irreplaceable. Force-inclusion tests whether the edge is compatible with optimality. Together they produce a complete classification.

The solution

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return 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(n, edges):
    indexed = [(u, v, w, i) for i, (u, v, w) in enumerate(edges)]
    indexed.sort(key=lambda x: x[2])

    def kruskal(n, edges, skip=-1, force=-1):
        uf = UnionFind(n)
        cost = 0
        count = 0
        if force >= 0:
            u, v, w, _ = indexed[force]
            uf.union(u, v)
            cost += w
            count += 1
        for j, (u, v, w, _) in enumerate(indexed):
            if j == skip:
                continue
            if uf.union(u, v):
                cost += w
                count += 1
        if count < n - 1:
            return float("inf")
        return cost

    base_cost = kruskal(n, indexed)
    critical = []
    pseudo = []

    for j in range(len(indexed)):
        if kruskal(n, indexed, skip=j) > base_cost:
            critical.append(indexed[j][3])
        elif kruskal(n, indexed, force=j) == base_cost:
            pseudo.append(indexed[j][3])

    return [critical, pseudo]

Here is how each piece works:

1. Index and sort: Attach the original index to each edge, then sort by weight. Kruskal's algorithm processes edges in weight order, and we need original indices for the output.

2. Union-Find with path compression and union by rank: The find method uses path halving (a variant of path compression). The union method attaches the smaller tree under the larger one. Both keep the amortized cost near O(alpha(n)).

3. Parameterized Kruskal's: The kruskal helper accepts skip and force parameters. If skip is set, that edge is excluded. If force is set, that edge is unioned first before processing the rest. This single function handles all three use cases (baseline, removal test, inclusion test).

4. Classification loop: For each edge, first test removal. If removing it raises the cost, it is critical. Otherwise, test force-inclusion. If forcing it keeps the cost at the baseline, it is pseudo-critical. Edges that fail both tests belong to no MST.

Visual walkthrough

The walkthrough uses the first LeetCode example: 5 nodes, 7 edges. Notice how the two weight-1 edges are both critical because removing either one forces the MST to pick a heavier alternative, raising the total cost from 7 to 8. The weight-2 and weight-3 edges are pseudo-critical because they are interchangeable with each other. Edge e6 (weight 6) is too heavy to appear in any MST.

Complexity analysis

We run Kruskal's algorithm once for the baseline and then twice per edge (once for removal, once for force-inclusion in the worst case). Each Kruskal's run takes O(E * alpha(V)) where alpha is the inverse Ackermann function. With E edges total, that gives O(E^2 * alpha(V)).

Space is O(V + E): the Union-Find structure uses O(V), and the sorted edge list uses O(E). We create a fresh Union-Find for each Kruskal's run, but only one exists at a time.

For the constraint bounds in this problem (V up to 100, E up to 200), this runs comfortably. For larger graphs, there are more advanced O(E * alpha(V)) algorithms using edge contraction, but the testing approach is the clearest to implement and explain.

The building blocks

1. Union-Find with path compression

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return 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

Union-Find is the backbone of Kruskal's algorithm. The find method uses path halving, where each node on the path skips one level up. This is simpler than full path compression and achieves the same amortized bound. The union method returns a boolean, which lets the caller know whether the edge actually connected two separate components or created a cycle.

2. Kruskal's algorithm for MST

def kruskal(n, sorted_edges):
    uf = UnionFind(n)
    cost = 0
    count = 0
    for u, v, w in sorted_edges:
        if uf.union(u, v):
            cost += w
            count += 1
    if count < n - 1:
        return float("inf")
    return cost

Kruskal's algorithm greedily adds the cheapest edge that does not form a cycle. If we process fewer than n-1 edges, the graph is disconnected and no spanning tree exists. Returning infinity for disconnected graphs simplifies the comparison logic in the classification step: any finite cost is better than infinity, so a removed edge that disconnects the graph is automatically classified as critical.

Edge cases

• Single node, no edges: With n=1, the MST is empty (cost 0, zero edges). Both critical and pseudo-critical lists are empty.
• All edges have the same weight: Every valid spanning tree has the same cost. No edge is critical (you can always swap one for another of equal weight), and every edge that can be part of some spanning tree is pseudo-critical.
• Bridge edges: An edge whose removal disconnects the graph is always critical, regardless of its weight. The removal test catches this because Kruskal's returns infinity for a disconnected graph.
• Parallel edges (same endpoints, different weights): Only the lighter one can be in an MST. The heavier parallel edge will fail the force-inclusion test because it raises the total cost.
• Tree graph (exactly n-1 edges): Every edge is critical because removing any edge disconnects the graph, and there is no alternative.
• Complete graph: Many edges are pseudo-critical because there are many spanning trees with the same cost. The classification loop correctly tests each edge individually.

From understanding to recall

The structure of this solution is simple once you see it: sort edges, run baseline Kruskal's, then test each edge with remove-and-rebuild and force-and-rebuild. But reproducing it from memory requires you to hold several details in your head at once. The Union-Find implementation, the parameterized Kruskal's function, the classification logic, and the edge case of disconnected graphs all need to come together smoothly.

The best way to practice is to break the solution into its building blocks. Write Union-Find from scratch until it is automatic. Then write Kruskal's. Then add the skip and force parameters. Each piece is small, but together they form a complete and correct solution.

Spaced repetition locks in the connections between these pieces. After a few review sessions, you will not need to think about whether union returns True or False, or whether to check count < n - 1. Those details become reflexive, freeing your working memory for the actual problem-solving during an interview.

Related posts

• Course Schedule - Graph traversal with topological sort, another core graph algorithm to pair with MST
• Minimum Genetic Mutation - BFS graph exploration with weighted transitions
• Number of Provinces - Connected components with Union-Find, the same data structure that powers Kruskal's algorithm

CodeBricks breaks Find Critical and Pseudo-Critical Edges in MST into its Union-Find, Kruskal's, and edge classification building blocks, then drills each one with spaced repetition. You type every piece from scratch until the pattern is automatic. When an MST or Union-Find problem shows up in your interview, you do not hesitate. You just write it.