Facebook Pixel

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

HardUnion FindGraphMinimum Spanning TreeSortingStrongly Connected Component
Leetcode Link

Problem Description

You are given a weighted undirected connected graph with n vertices (numbered from 0 to n-1) and an array edges. Each element edges[i] = [ai, bi, weighti] represents a bidirectional weighted edge between nodes ai and bi with weight weighti.

A Minimum Spanning Tree (MST) is a subset of the graph's edges that:

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

Your task is to identify two types of edges in relation to the MST:

  1. Critical Edges: These are edges that appear in every possible MST of the graph. If you remove a critical edge from the graph, the weight of the MST would increase (or it would become impossible to form an MST).

  2. Pseudo-Critical Edges: These are edges that appear in at least one MST but not in all MSTs. They can be part of some valid MSTs but are not essential.

You need to return two lists:

  • The first list contains the indices of all critical edges
  • The second list contains the indices of all pseudo-critical edges

The indices refer to the original positions of edges in the input edges array, and you can return them in any order within each list.

For example, if an edge at index 2 in the original edges array is critical, then 2 should appear in the first returned list. If an edge at index 5 can appear in some MSTs but not all, then 5 should appear in the second returned list.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To understand which edges are critical or pseudo-critical, we need to think about what makes an edge special in an MST.

First, let's establish a baseline - we need to know the weight of the actual MST. We can find this using a standard MST algorithm like Kruskal's (sorting edges by weight and using Union-Find to avoid cycles).

Now, how do we identify critical edges? A critical edge is one that must be in every MST. If we remove it from the graph entirely and try to build an MST without it, one of two things will happen:

  1. We can't connect all vertices anymore (the graph becomes disconnected)
  2. We can connect all vertices, but the total weight increases

This gives us our first test: for each edge, remove it from the graph and try to build an MST. If we can't build one with the same weight as the original MST, that edge is critical.

For pseudo-critical edges, we need a different approach. A pseudo-critical edge is one that can be part of an MST but isn't required. How do we test if an edge can be part of an MST? We can force it to be included!

Here's the key insight: if we force an edge to be in our spanning tree from the start (by including it first before running the MST algorithm), and the resulting total weight equals the original MST weight, then this edge can be part of at least one valid MST.

The strategy becomes:

  1. Calculate the original MST weight v
  2. For each edge:
    • Test if it's critical by excluding it and checking if we get a higher weight or disconnected graph
    • If it's not critical, test if it's pseudo-critical by forcing its inclusion and checking if we still get weight v

This approach cleverly uses the property that if an edge is neither critical nor pseudo-critical, forcing its inclusion would result in a spanning tree with weight greater than the MST weight (because we're forcing a suboptimal edge into the solution).

Learn more about Union Find, Graph, Minimum Spanning Tree and Sorting patterns.

Solution Approach

The implementation uses Kruskal's algorithm with Union-Find to build MSTs and test edges for criticality.

Step 1: Prepare the edges

for i, e in enumerate(edges):
    e.append(i)
edges.sort(key=lambda x: x[2])

We append the original index to each edge (so we can track which edge is which after sorting), then sort all edges by weight. This prepares us for Kruskal's algorithm.

Step 2: Calculate the original MST weight

uf = UnionFind(n)
v = sum(w for f, t, w, _ in edges if uf.union(f, t))

Using Union-Find, we build the MST by iterating through sorted edges. The union method returns True if the two nodes weren't already connected (edge is added to MST), False if they were (edge would create a cycle). We sum up weights of edges that were successfully added to get the MST weight v.

Step 3: Test each edge For each edge (f, t, w, i) where i is the original index:

Testing for Critical Edge:

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
  • Build an MST excluding edge i (condition j != i)
  • Check if the graph is still connected (uf.n == 1 means all nodes are in one component)
  • If disconnected (uf.n > 1) or if the new MST weight k is greater than v, the edge is critical

Testing for Pseudo-Critical Edge:

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)
  • Force the edge into the MST by calling uf.union(f, t) first
  • Add its weight w to the total
  • Build the rest of the MST excluding this edge from the iteration
  • If the final weight equals v, this edge can be part of an MST (pseudo-critical)

Union-Find Data Structure: The UnionFind class maintains:

  • p: parent array for each node
  • n: number of connected components (starts at n, decreases with each union)

The find method uses path compression for efficiency:

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

The union method connects two components and returns whether they were previously disconnected:

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

This approach efficiently identifies both critical and pseudo-critical edges in O(E² × α(V)) time, where E is the number of edges and α is the inverse Ackermann function (practically constant).

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Graph:

  • n = 4 (vertices: 0, 1, 2, 3)
  • edges = [[0,1,1], [1,2,1], [2,3,2], [0,3,2], [1,3,3]]

Step 1: Prepare edges with indices and sort by weight After appending original indices and sorting:

edges = [[0,1,1,0], [1,2,1,1], [2,3,2,2], [0,3,2,3], [1,3,3,4]]
         (from, to, weight, original_index)

Step 2: Calculate original MST weight Using Kruskal's algorithm with Union-Find:

  • Edge [0,1,1]: Connect 0-1, add to MST (weight = 1)
  • Edge [1,2,1]: Connect 1-2, add to MST (weight = 1)
  • Edge [2,3,2]: Connect 2-3, add to MST (weight = 2)
  • Edge [0,3,2]: Skip (would create cycle 0-1-2-3-0)
  • Edge [1,3,3]: Skip (would create cycle)

MST weight v = 1 + 1 + 2 = 4

Step 3: Test each edge

Testing edge 0 [0,1,1]:

  • Exclude it and build MST: Use edges [1,2,1], [2,3,2], [0,3,2] → weight = 5
  • Since 5 > 4, edge 0 is critical

Testing edge 1 [1,2,1]:

  • Exclude it and build MST: Use edges [0,1,1], [2,3,2], [0,3,2] → weight = 5
  • Since 5 > 4, edge 1 is critical

Testing edge 2 [2,3,2]:

  • Exclude it and build MST: Use edges [0,1,1], [1,2,1], [0,3,2], [1,3,3] → weight = 5
  • Since 5 > 4, edge 2 is critical

Testing edge 3 [0,3,2]:

  • Exclude it and build MST: Use edges [0,1,1], [1,2,1], [2,3,2] → weight = 4
  • Not critical (same weight without it)
  • Force include it: Start with [0,3,2], then add [0,1,1], [1,2,1] → weight = 4
  • Since weight equals v, edge 3 is pseudo-critical

Testing edge 4 [1,3,3]:

  • Exclude it and build MST: Use edges [0,1,1], [1,2,1], [2,3,2] → weight = 4
  • Not critical
  • Force include it: Start with [1,3,3], then add [0,1,1], [1,2,1] → weight = 5
  • Since 5 > 4, edge 4 is neither critical nor pseudo-critical

Result:

  • Critical edges: [0, 1, 2]
  • Pseudo-critical edges: [3]

This example demonstrates how the algorithm identifies edges that must appear in every MST (critical) versus edges that can appear in some MSTs but not all (pseudo-critical).

Solution Implementation

1from typing import List
2
3
4class UnionFind:
5    """Union-Find (Disjoint Set Union) data structure with path compression."""
6  
7    def __init__(self, n: int) -> None:
8        """Initialize n disjoint sets, each containing one element."""
9        self.parent = list(range(n))  # Each node is initially its own parent
10        self.num_components = n  # Number of connected components
11  
12    def union(self, node_a: int, node_b: int) -> bool:
13        """
14        Union two sets containing node_a and node_b.
15        Returns True if they were in different sets, False otherwise.
16        """
17        root_a = self.find(node_a)
18        root_b = self.find(node_b)
19      
20        if root_a == root_b:
21            return False  # Already in the same set
22      
23        # Merge the two sets by making one root point to the other
24        self.parent[root_a] = root_b
25        self.num_components -= 1
26        return True
27  
28    def find(self, node: int) -> int:
29        """
30        Find the root of the set containing node.
31        Applies path compression for optimization.
32        """
33        if self.parent[node] != node:
34            # Path compression: make all nodes point directly to root
35            self.parent[node] = self.find(self.parent[node])
36        return self.parent[node]
37
38
39class Solution:
40    def findCriticalAndPseudoCriticalEdges(
41        self, n: int, edges: List[List[int]]
42    ) -> List[List[int]]:
43        """
44        Find critical and pseudo-critical edges in an MST.
45      
46        Critical edge: MST weight increases if this edge is removed
47        Pseudo-critical edge: Can be in some MST but not critical
48      
49        Args:
50            n: Number of vertices
51            edges: List of edges [from, to, weight]
52      
53        Returns:
54            List containing two lists: [critical_edges, pseudo_critical_edges]
55        """
56        # Add original index to each edge to track them after sorting
57        for edge_idx, edge in enumerate(edges):
58            edge.append(edge_idx)
59      
60        # Sort edges by weight for Kruskal's algorithm
61        edges.sort(key=lambda edge: edge[2])
62      
63        # Find MST weight using standard Kruskal's algorithm
64        uf_mst = UnionFind(n)
65        mst_weight = 0
66        for from_node, to_node, weight, _ in edges:
67            if uf_mst.union(from_node, to_node):
68                mst_weight += weight
69      
70        critical_edges = []
71        pseudo_critical_edges = []
72      
73        # Check each edge to determine if it's critical or pseudo-critical
74        for from_node, to_node, weight, original_idx in edges:
75            # Test 1: Try building MST without this edge
76            uf_without = UnionFind(n)
77            weight_without = 0
78          
79            for curr_from, curr_to, curr_weight, curr_idx in edges:
80                if curr_idx != original_idx:  # Skip current edge
81                    if uf_without.union(curr_from, curr_to):
82                        weight_without += curr_weight
83          
84            # If graph is disconnected or weight increases, edge is critical
85            if uf_without.num_components > 1 or weight_without > mst_weight:
86                critical_edges.append(original_idx)
87                continue
88          
89            # Test 2: Force include this edge and build MST
90            uf_with = UnionFind(n)
91            uf_with.union(from_node, to_node)
92            weight_with = weight  # Start with current edge weight
93          
94            for curr_from, curr_to, curr_weight, curr_idx in edges:
95                if curr_idx != original_idx:  # Skip current edge (already included)
96                    if uf_with.union(curr_from, curr_to):
97                        weight_with += curr_weight
98          
99            # If MST weight remains same, edge is pseudo-critical
100            if weight_with == mst_weight:
101                pseudo_critical_edges.append(original_idx)
102      
103        return [critical_edges, pseudo_critical_edges]
104
1class Solution {
2    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
3        // Add original index to each edge for tracking
4        // Convert each edge from [u, v, weight] to [u, v, weight, originalIndex]
5        for (int i = 0; i < edges.length; ++i) {
6            int[] edge = edges[i];
7            int[] extendedEdge = new int[4];
8            System.arraycopy(edge, 0, extendedEdge, 0, 3);
9            extendedEdge[3] = i;  // Store original index
10            edges[i] = extendedEdge;
11        }
12      
13        // Sort edges by weight for Kruskal's algorithm
14        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
15      
16        // Find MST weight using standard Kruskal's algorithm
17        int mstWeight = 0;
18        UnionFind unionFind = new UnionFind(n);
19        for (int[] edge : edges) {
20            int from = edge[0];
21            int to = edge[1];
22            int weight = edge[2];
23          
24            // If union is successful (no cycle), add edge weight to MST
25            if (unionFind.union(from, to)) {
26                mstWeight += weight;
27            }
28        }
29      
30        // Initialize result lists: critical edges and pseudo-critical edges
31        List<List<Integer>> result = new ArrayList<>();
32        for (int i = 0; i < 2; ++i) {
33            result.add(new ArrayList<>());
34        }
35      
36        // Check each edge to determine if it's critical or pseudo-critical
37        for (int[] currentEdge : edges) {
38            int from = currentEdge[0];
39            int to = currentEdge[1];
40            int weight = currentEdge[2];
41            int originalIndex = currentEdge[3];
42          
43            // Test 1: Build MST without current edge to check if it's critical
44            unionFind = new UnionFind(n);
45            int weightWithoutEdge = 0;
46          
47            for (int[] edge : edges) {
48                int x = edge[0];
49                int y = edge[1];
50                int w = edge[2];
51                int index = edge[3];
52              
53                // Skip current edge
54                if (index != originalIndex && unionFind.union(x, y)) {
55                    weightWithoutEdge += w;
56                }
57            }
58          
59            // If graph is disconnected or MST weight increases, edge is critical
60            if (unionFind.getComponentCount() > 1 || 
61                (unionFind.getComponentCount() == 1 && weightWithoutEdge > mstWeight)) {
62                result.get(0).add(originalIndex);
63                continue;
64            }
65          
66            // Test 2: Force include current edge to check if it's pseudo-critical
67            unionFind = new UnionFind(n);
68            unionFind.union(from, to);  // Force include current edge
69            int weightWithEdge = weight;
70          
71            for (int[] edge : edges) {
72                int x = edge[0];
73                int y = edge[1];
74                int w = edge[2];
75                int index = edge[3];
76              
77                // Skip current edge (already included)
78                if (index != originalIndex && unionFind.union(x, y)) {
79                    weightWithEdge += w;
80                }
81            }
82          
83            // If MST weight remains same when forcing edge, it's pseudo-critical
84            if (weightWithEdge == mstWeight) {
85                result.get(1).add(originalIndex);
86            }
87        }
88      
89        return result;
90    }
91}
92
93class UnionFind {
94    private int[] parent;
95    private int componentCount;  // Number of disjoint components
96  
97    public UnionFind(int n) {
98        parent = new int[n];
99        this.componentCount = n;
100      
101        // Initially, each node is its own parent
102        for (int i = 0; i < n; ++i) {
103            parent[i] = i;
104        }
105    }
106  
107    public int getComponentCount() {
108        return componentCount;
109    }
110  
111    // Union two nodes, returns true if they were in different components
112    public boolean union(int a, int b) {
113        int rootA = find(a);
114        int rootB = find(b);
115      
116        // Already in same component
117        if (rootA == rootB) {
118            return false;
119        }
120      
121        // Merge components
122        parent[rootA] = rootB;
123        --componentCount;
124        return true;
125    }
126  
127    // Find root with path compression
128    public int find(int x) {
129        if (parent[x] != x) {
130            parent[x] = find(parent[x]);  // Path compression
131        }
132        return parent[x];
133    }
134}
135
1class UnionFind {
2public:
3    vector<int> parent;  // parent[i] represents the parent of node i
4    int componentCount;  // number of connected components
5  
6    // Initialize Union-Find with n nodes
7    UnionFind(int n) : componentCount(n), parent(n) {
8        // Initially, each node is its own parent (self-loop)
9        iota(parent.begin(), parent.end(), 0);
10    }
11  
12    // Unite two nodes and return true if they were in different components
13    bool unite(int nodeA, int nodeB) {
14        int rootA = find(nodeA);
15        int rootB = find(nodeB);
16      
17        // Already in the same component
18        if (rootA == rootB) {
19            return false;
20        }
21      
22        // Connect the two components by making one root point to the other
23        parent[rootA] = rootB;
24        componentCount--;
25        return true;
26    }
27  
28    // Find the root of a node with path compression
29    int find(int node) {
30        if (parent[node] != node) {
31            // Path compression: make every node point directly to root
32            parent[node] = find(parent[node]);
33        }
34        return parent[node];
35    }
36};
37
38class Solution {
39public:
40    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
41        // Add original index to each edge for tracking
42        for (int i = 0; i < edges.size(); ++i) {
43            edges[i].push_back(i);
44        }
45      
46        // Sort edges by weight in ascending order
47        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) { 
48            return a[2] < b[2]; 
49        });
50      
51        // Calculate MST weight using Kruskal's algorithm
52        int mstWeight = 0;
53        UnionFind uf(n);
54        for (const auto& edge : edges) {
55            int from = edge[0];
56            int to = edge[1];
57            int weight = edge[2];
58          
59            if (uf.unite(from, to)) {
60                mstWeight += weight;
61            }
62        }
63      
64        // Result arrays: [0] = critical edges, [1] = pseudo-critical edges
65        vector<vector<int>> result(2);
66      
67        // Check each edge to determine if it's critical or pseudo-critical
68        for (const auto& currentEdge : edges) {
69            int from = currentEdge[0];
70            int to = currentEdge[1];
71            int weight = currentEdge[2];
72            int originalIndex = currentEdge[3];
73          
74            // Test 1: Try to build MST without current edge
75            UnionFind ufWithoutEdge(n);
76            int weightWithoutEdge = 0;
77          
78            for (const auto& edge : edges) {
79                int x = edge[0];
80                int y = edge[1];
81                int w = edge[2];
82                int idx = edge[3];
83              
84                // Skip the current edge
85                if (idx != originalIndex && ufWithoutEdge.unite(x, y)) {
86                    weightWithoutEdge += w;
87                }
88            }
89          
90            // If graph is disconnected or MST weight increases, edge is critical
91            if (ufWithoutEdge.componentCount > 1 || 
92                (ufWithoutEdge.componentCount == 1 && weightWithoutEdge > mstWeight)) {
93                result[0].push_back(originalIndex);
94                continue;
95            }
96          
97            // Test 2: Force include current edge and build MST
98            UnionFind ufWithEdge(n);
99            ufWithEdge.unite(from, to);  // Force include current edge
100            int weightWithEdge = weight;
101          
102            for (const auto& edge : edges) {
103                int x = edge[0];
104                int y = edge[1];
105                int w = edge[2];
106                int idx = edge[3];
107              
108                // Skip the current edge (already included)
109                if (idx != originalIndex && ufWithEdge.unite(x, y)) {
110                    weightWithEdge += w;
111                }
112            }
113          
114            // If MST weight remains same, edge is pseudo-critical
115            if (weightWithEdge == mstWeight) {
116                result[1].push_back(originalIndex);
117            }
118        }
119      
120        return result;
121    }
122};
123
1// Union-Find data structure for tracking connected components
2let parent: number[];  // parent[i] represents the parent of node i
3let componentCount: number;  // number of connected components
4
5// Initialize Union-Find with n nodes
6function initializeUnionFind(n: number): void {
7    componentCount = n;
8    parent = new Array(n);
9    // Initially, each node is its own parent (self-loop)
10    for (let i = 0; i < n; i++) {
11        parent[i] = i;
12    }
13}
14
15// Find the root of a node with path compression
16function find(node: number): number {
17    if (parent[node] !== node) {
18        // Path compression: make every node point directly to root
19        parent[node] = find(parent[node]);
20    }
21    return parent[node];
22}
23
24// Unite two nodes and return true if they were in different components
25function unite(nodeA: number, nodeB: number): boolean {
26    const rootA = find(nodeA);
27    const rootB = find(nodeB);
28  
29    // Already in the same component
30    if (rootA === rootB) {
31        return false;
32    }
33  
34    // Connect the two components by making one root point to the other
35    parent[rootA] = rootB;
36    componentCount--;
37    return true;
38}
39
40function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
41    // Add original index to each edge for tracking
42    for (let i = 0; i < edges.length; i++) {
43        edges[i].push(i);
44    }
45  
46    // Sort edges by weight in ascending order
47    edges.sort((a, b) => a[2] - b[2]);
48  
49    // Calculate MST weight using Kruskal's algorithm
50    let mstWeight = 0;
51    initializeUnionFind(n);
52  
53    for (const edge of edges) {
54        const from = edge[0];
55        const to = edge[1];
56        const weight = edge[2];
57      
58        if (unite(from, to)) {
59            mstWeight += weight;
60        }
61    }
62  
63    // Result arrays: [0] = critical edges, [1] = pseudo-critical edges
64    const result: number[][] = [[], []];
65  
66    // Check each edge to determine if it's critical or pseudo-critical
67    for (const currentEdge of edges) {
68        const from = currentEdge[0];
69        const to = currentEdge[1];
70        const weight = currentEdge[2];
71        const originalIndex = currentEdge[3];
72      
73        // Test 1: Try to build MST without current edge
74        initializeUnionFind(n);
75        let weightWithoutEdge = 0;
76      
77        for (const edge of edges) {
78            const x = edge[0];
79            const y = edge[1];
80            const w = edge[2];
81            const idx = edge[3];
82          
83            // Skip the current edge
84            if (idx !== originalIndex && unite(x, y)) {
85                weightWithoutEdge += w;
86            }
87        }
88      
89        // If graph is disconnected or MST weight increases, edge is critical
90        if (componentCount > 1 || 
91            (componentCount === 1 && weightWithoutEdge > mstWeight)) {
92            result[0].push(originalIndex);
93            continue;
94        }
95      
96        // Test 2: Force include current edge and build MST
97        initializeUnionFind(n);
98        unite(from, to);  // Force include current edge
99        let weightWithEdge = weight;
100      
101        for (const edge of edges) {
102            const x = edge[0];
103            const y = edge[1];
104            const w = edge[2];
105            const idx = edge[3];
106          
107            // Skip the current edge (already included)
108            if (idx !== originalIndex && unite(x, y)) {
109                weightWithEdge += w;
110            }
111        }
112      
113        // If MST weight remains same, edge is pseudo-critical
114        if (weightWithEdge === mstWeight) {
115            result[1].push(originalIndex);
116        }
117    }
118  
119    return result;
120}
121

Time and Space Complexity

Time Complexity: O(E² * α(V)) where E is the number of edges, V is the number of vertices, and α is the inverse Ackermann function.

  • Sorting edges takes O(E log E)
  • Finding the MST weight initially requires O(E * α(V)) operations
  • For each edge (total E edges), we perform:
    • First check (excluding edge): iterate through all edges performing union-find operations, which takes O(E * α(V))
    • Second check (forcing edge): iterate through all edges performing union-find operations, which takes O(E * α(V))
  • Overall: O(E log E) + O(E * α(V)) + E * O(E * α(V)) = O(E² * α(V))

Since α(V) grows extremely slowly and is effectively constant for practical purposes, the time complexity can be approximated as O(E²).

Space Complexity: O(E + V)

  • Modified edges list with indices: O(E) (adding one index per edge)
  • UnionFind data structure: O(V) for the parent array
  • The algorithm creates new UnionFind instances for each edge check, but only one exists at a time
  • Result lists store at most E indices: O(E)
  • Overall space complexity: O(E + V)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Track Original Edge Indices

One of the most common mistakes is sorting the edges by weight without preserving the original indices. Since the problem asks for the indices from the original input array, losing track of these indices after sorting will produce incorrect results.

Incorrect approach:

edges.sort(key=lambda x: x[2])  # Original indices are lost!
# Later trying to return edge positions won't match original input

Correct approach:

# Append original index before sorting
for i, edge in enumerate(edges):
    edge.append(i)
edges.sort(key=lambda x: x[2])
# Now edge[3] contains the original index

2. Incorrectly Determining Graph Connectivity

When testing if an edge is critical by excluding it, developers often check only the MST weight but forget to verify if the graph remains connected. An edge is critical if removing it either disconnects the graph OR increases the MST weight.

Incorrect approach:

# Only checking weight difference
if weight_without > mst_weight:
    critical_edges.append(i)

Correct approach:

# Check both disconnection AND weight increase
if uf_without.num_components > 1 or weight_without > mst_weight:
    critical_edges.append(i)

3. Not Properly Forcing Edge Inclusion for Pseudo-Critical Test

When testing if an edge is pseudo-critical, you must force it into the MST first, then build the rest. A common mistake is to just prioritize it during the normal MST construction process, which doesn't guarantee its inclusion.

Incorrect approach:

# Just trying to use the edge first doesn't guarantee inclusion
uf_with = UnionFind(n)
weight_with = 0
# Process current edge first
if uf_with.union(from_node, to_node):
    weight_with += weight
# Then process others... but the edge might already be redundant!

Correct approach:

# Force the edge inclusion first
uf_with = UnionFind(n)
uf_with.union(from_node, to_node)  # Force union
weight_with = weight  # Always add its weight
# Then build the rest of MST
for curr_from, curr_to, curr_weight, curr_idx in edges:
    if curr_idx != original_idx:
        if uf_with.union(curr_from, curr_to):
            weight_with += curr_weight

4. Edge Classification Logic Error

Some implementations mistakenly classify edges as both critical and pseudo-critical, or miss the fact that these are mutually exclusive categories. Once an edge is identified as critical, it should not be tested for pseudo-critical status.

Incorrect approach:

for edge in edges:
    if is_critical(edge):
        critical_edges.append(edge)
    if is_pseudo_critical(edge):  # Wrong! Should not test if already critical
        pseudo_critical_edges.append(edge)

Correct approach:

for edge in edges:
    if is_critical(edge):
        critical_edges.append(edge)
        continue  # Skip pseudo-critical test
    if is_pseudo_critical(edge):
        pseudo_critical_edges.append(edge)

5. Union-Find Path Compression Implementation Error

A subtle but impactful mistake in the Union-Find implementation is forgetting to update the parent during path compression, leading to inefficient operations.

Incorrect approach:

def find(self, x):
    if self.parent[x] != x:
        return self.find(self.parent[x])  # No path compression!
    return self.parent[x]

Correct approach:

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # Path compression
    return self.parent[x]

These pitfalls can lead to incorrect classification of edges, time limit exceeded errors, or runtime errors. Always ensure proper index tracking, complete connectivity checks, and correct edge forcing logic when implementing this algorithm.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Graph Fundamentals

https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree

Minimum Spanning Tree | Forests

Minimum Spanning Tree Forests The Umbristan Department of Forestry UDF is tackling a rather difficult problem and the Umbristan government has assigned you as one of its best workers to go resolve the issue When you arrive you are quickly briefed on the problem at hand Inside the Umbristan National Park there exists an

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More