#1489

Hard

LeetCode Problem Workspace

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Identify critical and pseudo-critical edges in a weighted graph's minimum spanning tree using Union Find efficiently.

union find graph sorting minimum spanning tree strongly connected component

Problem Statement

Given a connected undirected graph with n vertices numbered from 0 to n - 1, and a list of weighted edges edges where edges[i] = [ai, bi, weighti] represents a bidirectional edge connecting ai and bi with weight weighti, determine properties of its minimum spanning tree (MST). An MST connects all vertices with no cycles and minimal total weight.

Your task is to find all critical and pseudo-critical edges in the MST. A critical edge is one whose removal increases the MST weight, while a pseudo-critical edge can appear in some MSTs but not all. Return two lists of edge indices, first for critical and second for pseudo-critical edges, in any order.

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

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

The figure above describes the graph. The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output. The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2

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

Output: [[],[0,1,2,3]]

We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

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.

Solution Approach

Compute the base MST using Kruskal and Union Find

Sort all edges by weight and use Union Find to add edges without forming cycles. Record the total MST weight as the reference. This ensures correct detection of critical edges by providing a baseline for comparison.

Identify critical edges

For each edge, temporarily remove it and recompute the MST with remaining edges using Union Find. If the new MST weight exceeds the baseline, mark this edge as critical. This directly applies the failure mode check unique to this problem.

Identify pseudo-critical edges

Force include each edge and compute MST with Union Find. If MST forms with the same total weight as baseline, classify the edge as pseudo-critical. This ensures edges optionally part of some MSTs are correctly distinguished.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on sorting edges O(E log E) and running Union Find operations for each edge O(E * α(n)) where α is the inverse Ackermann function, yielding roughly O(E log E + E * α(n)). Space complexity is O(n + E) for Union Find parent and rank arrays.

What Interviewers Usually Probe

Using Union Find plus Kruskal is expected to compute MST efficiently.
Checking MST weight changes when removing edges indicates criticality understanding.
Forcing edges in MST tests pseudo-critical behavior and optional inclusion reasoning.

Common Pitfalls or Variants

Common pitfalls

Failing to sort edges before applying Union Find can give incorrect MST weight.
Not restoring Union Find state correctly between tests may misclassify edges.
Confusing critical with pseudo-critical edges due to MST weight comparison errors.

Follow-up variants

Determine all edges that appear in any MST of a graph, regardless of weight uniqueness.
Count the number of distinct MSTs in a weighted graph using Union Find plus combinatorial checks.
Find critical edges in a directed weighted graph where minimum spanning arborescence is required.

FAQ

What defines a critical edge in the 'Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree' problem?

A critical edge is one whose removal causes the MST weight to increase, meaning it appears in all MSTs of the graph.

How do pseudo-critical edges differ from critical edges?

Pseudo-critical edges can appear in some MSTs but are not required in every MST, unlike critical edges which are always necessary.

Which algorithm pattern is most effective for this problem?

The Union Find plus Graph pattern using Kruskal's algorithm efficiently computes MST and identifies critical and pseudo-critical edges.

Can edges be returned in any order?

Yes, the problem allows returning edge indices in any order for both critical and pseudo-critical lists.

What are the main failure modes to watch for in this problem?

Incorrectly updating Union Find state, misclassifying edges, or ignoring weight comparisons when testing edges can cause wrong MST classification.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.n = n

    def union(self, a, b):
        if self.find(a) == self.find(b):
            return False
        self.p[self.find(a)] = self.find(b)
        self.n -= 1
        return True

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]


class Solution:
    def findCriticalAndPseudoCriticalEdges(
        self, n: int, edges: List[List[int]]
    ) -> List[List[int]]:
        for i, e in enumerate(edges):
            e.append(i)
        edges.sort(key=lambda x: x[2])
        uf = UnionFind(n)
        v = sum(w for f, t, w, _ in edges if uf.union(f, t))
        ans = [[], []]
        for f, t, w, i in edges:
            uf = UnionFind(n)
            k = sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
            if uf.n > 1 or (uf.n == 1 and k > v):
                ans[0].append(i)
                continue

            uf = UnionFind(n)
            uf.union(f, t)
            k = w + sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
            if k == v:
                ans[1].append(i)
        return ans

Continue Practicing

#1584 min cost to connect all points #1632 rank transform of a matrix #1697 checking existence of edge length limited paths