How to Solve Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Start by computing the MST weight with Kruskal's algorithm and Union Find to track connected components. Test each edge by temporarily removing it to see if the MST weight increases, marking it as critical. For pseudo-critical edges, forcibly include the edge and check if a valid MST with the same total weight forms. This approach separates edges that are always necessary from those optionally used in MSTs.

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

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.

How GhostInterview Helps

• Automatically separates critical and pseudo-critical edges using Kruskal and Union Find logic.
• Provides step-by-step edge testing to verify MST weight changes for this exact problem pattern.
• Highlights misclassification risks and failure modes unique to MST edge analysis.

Topic Pages

• Union Find
• Graph
• Sorting
• Minimum Spanning Tree
• Strongly Connected Component

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.