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

LeetCode Problem 1489

Difficulty: 🔴 Hard
Topics: Union-Find, Graph Theory, Sorting, Minimum Spanning Tree, Strongly Connected Component

Solution

Problem Understanding

The problem gives us a connected, weighted, undirected graph with n vertices and a list of edges. Each edge is represented as [u, v, weight], meaning there is a bidirectional connection between vertices u and v with the given cost.

The goal is not simply to compute one Minimum Spanning Tree (MST). Instead, we must classify every edge into one of two categories:

• Critical edges
• Pseudo-critical edges

To understand these categories, we first need to recall what an MST is.

An MST is a subset of edges that:

• Connects all vertices
• Contains no cycles
• Has the minimum possible total weight

A connected graph may have multiple different MSTs if several edges share the same weight.

A critical edge is an edge that must appear in every valid MST. If removing this edge causes the minimum achievable MST weight to increase, or makes it impossible to form a spanning tree at all, then the edge is critical.

A pseudo-critical edge is an edge that can appear in at least one MST, but is not required in all MSTs. In other words, there exists some optimal MST containing this edge, but there also exists another optimal MST without it.

The output must contain two lists:

• The first list contains all critical edge indices
• The second list contains all pseudo-critical edge indices

The original edge indices matter, because the edges will be sorted internally during processing.

The constraints are important:

• n <= 100
• edges.length <= 200

These limits are small enough that we can afford to run MST construction multiple times. A highly optimized near-linear MST algorithm is unnecessary here. Instead, we can repeatedly run Kruskal's algorithm under different conditions.

Some important edge cases immediately stand out:

• Multiple edges can have the same weight, leading to multiple valid MSTs
• An edge may appear optional even though it looks important locally
• Removing certain edges may disconnect the graph entirely
• Dense graphs with many equal-weight edges can produce many pseudo-critical edges
• The graph is guaranteed to be connected initially, which means at least one MST always exists

The key challenge is determining how each edge affects the structure and cost of the MST.

Approaches

Brute Force Approach

The brute-force idea is to enumerate every possible spanning tree of the graph, compute its total weight, determine the minimum among them, and then inspect which edges appear in all minimum spanning trees versus only some.

A spanning tree for n vertices contains exactly n - 1 edges. We could theoretically generate every combination of n - 1 edges, check whether it forms a valid spanning tree, compute its weight, and compare it against the global minimum.

This works because the definitions of critical and pseudo-critical edges are directly based on the set of all MSTs.

However, this approach is computationally infeasible. A graph with up to 200 edges would require checking an enormous number of edge subsets:

$$\binom{200}{99}$$

Even validating each subset would require graph traversal or Union-Find operations. The total runtime becomes astronomically large.

Optimal Approach

The key insight is that we do not need to enumerate all MSTs. Instead, we can leverage properties of Kruskal's algorithm.

Kruskal's algorithm constructs an MST by:

1. Sorting edges by weight
2. Adding edges greedily if they do not create a cycle

This produces one valid MST.

Now consider an edge e.

To determine whether e is critical:

• Remove e
• Recompute the MST
• If the new MST weight increases, or no MST exists, then e is critical

Why does this work?

Because if excluding e forces a more expensive spanning tree, then every optimal MST must contain e.

To determine whether e is pseudo-critical:

• Force e to be included first
• Then complete the MST normally using Kruskal
• If the resulting MST has the same total weight as the original MST, then e can belong to some MST

This works because we explicitly construct an optimal MST containing that edge.

The constraints are small enough that running Kruskal once per edge is completely acceptable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates all spanning trees
Optimal	O(E² log E)	O(E)	Repeated Kruskal with include/exclude checks

Algorithm Walkthrough

Step 1: Attach Original Indices

The edges will be sorted by weight, but the answer must return original indices.

We therefore transform each edge from:

[u, v, w]

into:

[u, v, w, original_index]

This allows us to sort edges while still remembering their positions in the input.

Step 2: Sort Edges by Weight

Kruskal's algorithm requires edges to be processed in non-decreasing order of weight.

Sorting ensures that we always attempt to add the cheapest valid edge first.

Step 3: Implement Union-Find

Union-Find, also called Disjoint Set Union (DSU), efficiently tracks connected components.

We need two operations:

• find(x) returns the representative of a component
• union(x, y) merges two components if they are different

Union-Find is ideal here because Kruskal repeatedly asks:

• Are these vertices already connected?
• If not, merge them

Using path compression and union by rank keeps operations nearly constant time.

Step 4: Build a Generic Kruskal Function

We create a helper function that computes MST weight under two optional conditions:

• Exclude a specific edge
• Force include a specific edge

This abstraction avoids duplicating MST logic.

The function works as follows:

1. Initialize DSU
2. If an edge must be included:

• Add its weight
• Union its endpoints

3. Iterate through all sorted edges
4. Skip excluded edges
5. Add edges that connect different components
6. Track total MST weight and edge count
7. If we fail to connect all vertices, return infinity

Returning infinity is useful because disconnected graphs cannot form valid MSTs.

Step 5: Compute the Baseline MST Weight

Run standard Kruskal once without exclusions or forced edges.

This gives the minimum possible MST weight for the graph.

Call this:

base_weight

All later comparisons are measured against this value.

Step 6: Identify Critical Edges

For each edge:

1. Recompute MST while excluding that edge
2. Compare the resulting weight with base_weight

If:

new_weight > base_weight

or the graph becomes disconnected, then the edge is critical.

This means the edge is indispensable for achieving the minimum cost.

Step 7: Identify Pseudo-Critical Edges

For each non-critical edge:

1. Force the edge into the MST
2. Complete MST construction normally
3. Compare total weight against base_weight

If the weight remains equal, then the edge can participate in some optimal MST.

Therefore it is pseudo-critical.

Why it works

Kruskal's algorithm always constructs an MST with minimum possible weight.

If removing an edge increases the optimal weight, then every MST must contain that edge, making it critical.

If forcing an edge still allows construction of an MST with optimal weight, then at least one valid MST contains it, making it pseudo-critical.

These checks directly match the mathematical definitions of the two categories.

Python Solution

from typing import List

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

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False

        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x

        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        return True

class Solution:
    def findCriticalAndPseudoCriticalEdges(
        self,
        n: int,
        edges: List[List[int]]
    ) -> List[List[int]]:

        indexed_edges = []

        for index, (u, v, w) in enumerate(edges):
            indexed_edges.append([u, v, w, index])

        indexed_edges.sort(key=lambda edge: edge[2])

        def kruskal(exclude_edge: int = -1,
                    include_edge: int = -1) -> int:

            uf = UnionFind(n)
            total_weight = 0
            edges_used = 0

            if include_edge != -1:
                u, v, w, _ = indexed_edges[include_edge]

                if uf.union(u, v):
                    total_weight += w
                    edges_used += 1

            for i, (u, v, w, _) in enumerate(indexed_edges):

                if i == exclude_edge:
                    continue

                if uf.union(u, v):
                    total_weight += w
                    edges_used += 1

                if edges_used == n - 1:
                    break

            if edges_used != n - 1:
                return float("inf")

            return total_weight

        base_weight = kruskal()

        critical = []
        pseudo_critical = []

        for i in range(len(indexed_edges)):

            if kruskal(exclude_edge=i) > base_weight:
                critical.append(indexed_edges[i][3])

            elif kruskal(include_edge=i) == base_weight:
                pseudo_critical.append(indexed_edges[i][3])

        return [critical, pseudo_critical]

The implementation begins by augmenting each edge with its original index. This is necessary because sorting changes edge order, but the output must reference original positions.

The UnionFind class supports efficient connectivity checks during MST construction. Path compression optimizes repeated find operations, while union by rank prevents the trees from becoming unbalanced.

The kruskal helper function is the core of the solution. It supports two optional behaviors:

• Excluding one edge
• Forcing one edge into the MST

If an edge is forced, it is added before normal processing begins. The rest of the edges are then processed in sorted order exactly as standard Kruskal would.

The helper returns infinity when the graph cannot become fully connected. This allows disconnected cases to automatically fail comparison checks.

The baseline MST weight is computed once. Then every edge undergoes two tests:

• Exclusion test for criticality
• Inclusion test for pseudo-criticality

The final answer contains the original edge indices in their respective categories.

Go Solution

package main

import "sort"

type UnionFind struct {
	parent []int
	rank   []int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	return &UnionFind{
		parent: parent,
		rank:   rank,
	}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x])
	}

	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
	rootX := uf.Find(x)
	rootY := uf.Find(y)

	if rootX == rootY {
		return false
	}

	if uf.rank[rootX] < uf.rank[rootY] {
		rootX, rootY = rootY, rootX
	}

	uf.parent[rootY] = rootX

	if uf.rank[rootX] == uf.rank[rootY] {
		uf.rank[rootX]++
	}

	return true
}

func findCriticalAndPseudoCriticalEdges(n int, edges [][]int) [][]int {

	indexedEdges := make([][]int, 0)

	for i, edge := range edges {
		indexedEdges = append(indexedEdges,
			[]int{edge[0], edge[1], edge[2], i})
	}

	sort.Slice(indexedEdges, func(i, j int) bool {
		return indexedEdges[i][2] < indexedEdges[j][2]
	})

	kruskal := func(excludeEdge int, includeEdge int) int {

		uf := NewUnionFind(n)

		totalWeight := 0
		edgesUsed := 0

		if includeEdge != -1 {
			edge := indexedEdges[includeEdge]

			if uf.Union(edge[0], edge[1]) {
				totalWeight += edge[2]
				edgesUsed++
			}
		}

		for i, edge := range indexedEdges {

			if i == excludeEdge {
				continue
			}

			if uf.Union(edge[0], edge[1]) {
				totalWeight += edge[2]
				edgesUsed++
			}

			if edgesUsed == n-1 {
				break
			}
		}

		if edgesUsed != n-1 {
			return 1 << 30
		}

		return totalWeight
	}

	baseWeight := kruskal(-1, -1)

	critical := []int{}
	pseudoCritical := []int{}

	for i := 0; i < len(indexedEdges); i++ {

		if kruskal(i, -1) > baseWeight {
			critical = append(critical, indexedEdges[i][3])
		} else if kruskal(-1, i) == baseWeight {
			pseudoCritical = append(
				pseudoCritical,
				indexedEdges[i][3],
			)
		}
	}

	return [][]int{critical, pseudoCritical}
}

The Go implementation follows the same logic as the Python version, but there are a few language-specific differences.

Go does not support classes directly, so UnionFind is implemented as a struct with associated methods.

Slices are used instead of Python lists. Since Go arrays have fixed size semantics, slices provide the required flexibility for dynamic edge storage.

The disconnected graph case returns a large sentinel value (1 << 30) instead of infinity, because Go integers do not support special floating-point infinity values for integer arithmetic.

Go also requires explicit sorting using sort.Slice, while Python can sort directly with a key function.

Worked Examples

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]
]

After adding indices and sorting:

Sorted Position	Edge	Weight	Original Index
0	[0,1]	1	0
1	[1,2]	1	1
2	[2,3]	2	2
3	[0,3]	2	3
4	[0,4]	3	4
5	[3,4]	3	5
6	[1,4]	6	6

Baseline MST Construction

Step	Edge	Action	Total Weight
1	[0,1]	Add	1
2	[1,2]	Add	2
3	[2,3]	Add	4
4	[0,3]	Skip cycle	4
5	[0,4]	Add	7

Baseline MST weight:

7

Testing Edge 0

Exclude edge 0:

• MST weight becomes larger than 7
• Therefore edge 0 is critical

Testing Edge 2

Force include edge 2:

Step	Edge	Action	Total
1	[2,3]	Forced include	2
2	[0,1]	Add	3
3	[1,2]	Add	4
4	[0,4]	Add	7

The MST weight remains 7, so edge 2 is pseudo-critical.

Final result:

Critical: [0,1]
Pseudo-critical: [2,3,4,5]

Example 2

Input:

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

All edges have equal weight.

Any three edges form an MST with weight 3.

Excluding any single edge still allows another MST with the same cost.

Therefore:

• No edge is critical
• Every edge is pseudo-critical

Result:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E² log E)	Run Kruskal for each edge
Space	O(E + N)	Edge storage plus Union-Find

The graph contains at most 200 edges, so repeatedly running Kruskal is entirely feasible.

Sorting costs:

$$O(E \log E)$$

Each Kruskal run processes all edges with nearly constant-time DSU operations.

We run Kruskal up to 2E + 1 times:

• Once for baseline MST
• Once per edge exclusion
• Once per edge inclusion

This gives overall complexity:

$$O(E^2 \log E)$$

The space usage comes primarily from:

• The sorted edge list
• The Union-Find parent and rank arrays

Test Cases

from typing import List

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        pass

sol = Solution()

# Example 1
assert sorted(sol.findCriticalAndPseudoCriticalEdges(
    5,
    [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
)[0]) == [0,1]  # critical edges

# Example 2
assert sorted(sol.findCriticalAndPseudoCriticalEdges(
    4,
    [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
)[1]) == [0,1,2,3]  # all pseudo-critical

# Smallest valid graph
assert sol.findCriticalAndPseudoCriticalEdges(
    2,
    [[0,1,5]]
) == [[0], []]  # single edge must be critical

# Unique MST
assert sorted(sol.findCriticalAndPseudoCriticalEdges(
    4,
    [[0,1,1],[1,2,2],[2,3,3],[0,3,10]]
)[0]) == [0,1,2]  # all MST edges critical

# Dense equal-weight graph
assert sorted(sol.findCriticalAndPseudoCriticalEdges(
    4,
    [[0,1,1],[0,2,1],[0,3,1],[1,2,1],[1,3,1],[2,3,1]]
)[1]) == [0,1,2,3,4,5]  # every edge pseudo-critical

# Edge never in any MST
result = sol.findCriticalAndPseudoCriticalEdges(
    3,
    [[0,1,1],[1,2,1],[0,2,100]]
)

assert 2 not in result[0]
assert 2 not in result[1]  # expensive edge excluded from all MSTs

# Graph with multiple pseudo-critical edges
result = sol.findCriticalAndPseudoCriticalEdges(
    5,
    [[0,1,1],[1,2,1],[2,3,1],[3,4,1],[0,4,1]]
)

assert sorted(result[1]) == [0,1,2,3,4]  # cycle with equal weights

Test	Why
Example 1	Validates both critical and pseudo-critical detection
Example 2	Confirms handling of multiple equal-weight MSTs
Single edge graph	Tests minimum constraints
Unique MST	Ensures required edges become critical
Dense equal weights	Ensures all edges become pseudo-critical
Expensive edge	Confirms non-MST edges are ignored
Equal-weight cycle	Tests multiple interchangeable MST structures

Edge Cases

One important edge case occurs when the graph has exactly one possible MST. In this situation, every edge in the MST is automatically critical because removing any one of them either disconnects the graph or forces the use of a more expensive edge. A buggy implementation may accidentally classify such edges as pseudo-critical if it only checks whether an edge can appear in an MST. This solution avoids that issue by always checking criticality first through exclusion testing.

Another important case involves graphs where many edges share the same weight. Equal weights create multiple valid MSTs, which means some edges may appear optional even though they frequently participate in optimal solutions. A naive greedy implementation could incorrectly assume the first selected edge is mandatory. By forcing inclusion and recomputing the MST independently, this implementation correctly identifies pseudo-critical edges.

A third edge case occurs when excluding an edge disconnects the graph entirely. In that scenario, no spanning tree can be formed. Some implementations mistakenly compare incomplete MST weights against the baseline and fail to recognize disconnection as evidence of criticality. This solution explicitly checks whether exactly n - 1 edges were used. If not, it returns infinity, guaranteeing that disconnected cases are treated as critical failures.

A subtle edge case involves edges that never belong to any MST. For example, a very expensive edge connecting vertices already reachable through cheaper paths should not be marked critical or pseudo-critical. The forced-inclusion test naturally filters these out because including such an edge increases the total MST weight beyond the baseline.