Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
HardPrompt
Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.
Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
Note that you can return the indices of the edges in any order.
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]]
Explanation: 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]]
Explanation: 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 <= 1001 <= edges.length <= min(200, n * (n - 1) / 2)edges[i].length == 30 <= ai < bi < n1 <= weighti <= 1000- All pairs
(ai, bi)are distinct.
Approaches
3 approaches with complexity analysis and trade-offs.
This highly efficient approach avoids recomputing MSTs from scratch by processing edges in groups of the same weight. It uses a Disjoint Set Union (DSU) structure to keep track of connected components. For each weight level, it identifies candidate edges that could be in an MST. It then analyzes these candidates in a temporary 'component graph' to distinguish critical edges (bridges) from pseudo-critical ones (non-bridges in cycles).
Algorithm
- Augment edges with original indices and sort them by weight.
- Initialize a DSU data structure.
- Iterate through the sorted edges in blocks of the same weight.
- For each block of edges with weight
w:- Find Candidates: For each edge
(u, v)in the block, check if its endpointsuandvare already connected in the DSU (which represents components formed by edges lighter thanw). Iffind(u) != find(v), this edge is a candidate for being in an MST. Collect all such candidates. - Build Component Graph: Construct a temporary graph where vertices are the connected components (represented by their roots in the DSU) and edges are the candidate edges found in the previous step.
- Find Bridges: Run a bridge-finding algorithm (like Tarjan's) on this component graph. Any candidate edge that is a bridge in this graph is a critical edge for the original problem.
- Identify Pseudo-Critical: Any candidate edge that is not a bridge is a pseudo-critical edge.
- Update DSU: After processing the block, update the main DSU by uniting the components for all edges in the current block. This prepares the DSU for the next, heavier block of edges.
- Find Candidates: For each edge
Walkthrough
This algorithm leverages the properties of Kruskal's algorithm and graph theory to achieve optimal performance. After sorting edges by weight, we process them in batches of equal weight.
At any point, our DSU structure represents the connected components formed by all edges lighter than the current batch's weight w. An edge (u, v) with weight w can only be in an MST if u and v belong to different components. These are our 'candidate' edges.
Now, we focus only on these candidates and the components they connect. We can think of this as a new, smaller graph. In this graph, if a candidate edge is the only way to connect two components at this weight level, it's a critical edge. In graph terms, this means the edge is a bridge. If there are multiple ways to connect two components (i.e., a cycle of candidate edges), then all edges in that cycle are interchangeable. They are part of some MSTs but not all, making them pseudo-critical.
We can use a standard algorithm like Tarjan's bridge-finding algorithm on this temporary component graph to classify the candidates. After classifying all edges in the batch, we merge the components they connect in our main DSU and move to the next batch of heavier edges.
Complexity
Time
O(m log m). Sorting the edges takes `O(m log m)`. The rest of the algorithm, including all DSU operations and the sum of all bridge-finding executions, takes `O(m * α(n))`. Therefore, the sorting step is the bottleneck.
Space
O(m + n) to store edges, the DSU, and the temporary data structures for the component graph and bridge-finding algorithm.
Trade-offs
Pros
The most efficient algorithm with a time complexity dominated by the initial sort.
Scales well to much larger inputs than the other approaches.
Cons
Significantly more complex to implement due to the need for a bridge-finding algorithm and management of the component graph.
This approach improves upon the naive brute-force method by eliminating the redundant sorting step. The edges are sorted by weight once at the beginning. Then, to check each edge, we iterate through the pre-sorted list to build the MST, which is significantly faster than creating and re-sorting a new list of edges for every check.
Algorithm
- First, augment the edges array to store the original index of each edge:
[u, v, weight, original_index]. - Sort this new array of edges based on weight. This is done only once.
- Calculate the original MST weight,
minMSTWeight, by running Kruskal's algorithm on the sorted edges. - Initialize two lists,
criticalandpseudoCritical. - Iterate through each edge
ifrom0tom-1:- To check for criticality: Calculate the MST weight of the graph while ignoring edge
i. If this weight is greater thanminMSTWeight, add the original index of edgeito thecriticallist. - To check for pseudo-criticality: If edge
iis not critical, calculate the MST weight while forcing the inclusion of edgei. If this weight is equal tominMSTWeight, add the original index of edgeito thepseudoCriticallist.
- To check for criticality: Calculate the MST weight of the graph while ignoring edge
- The MST calculations in the loop are done on the pre-sorted list of edges, avoiding the expensive re-sorting step.
Walkthrough
The logic remains the same as the brute-force approach: find a baseline MST weight, then test each edge by excluding it or forcing it. The key optimization comes from pre-sorting. By sorting all edges (along with their original indices) upfront, we can avoid the O(m log m) cost inside the main loop.
When we need to calculate an MST without an edge i, we simply iterate through our sorted edge list and skip i. This MST construction, using a Disjoint Set Union (DSU) data structure, takes O(m * α(n)), where α(n) is the very slow-growing inverse Ackermann function.
Similarly, to force an edge i, we pre-emptively union its vertices in the DSU and add its weight, then proceed with Kruskal's on the rest of the sorted edges. This also takes O(m * α(n)). Since we do this for all m edges, the total time complexity becomes O(m² * α(n)), which is a significant improvement over O(m² log m).
class Solution { public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) { int m = edges.length; int[][] newEdges = new int[m][4]; for (int i = 0; i < m; i++) { newEdges[i][0] = edges[i][0]; newEdges[i][1] = edges[i][1]; newEdges[i][2] = edges[i][2]; newEdges[i][3] = i; } Arrays.sort(newEdges, (a, b) -> Integer.compare(a[2], b[2])); int minMSTWeight = getMSTWeight(n, newEdges, -1, -1); List<Integer> critical = new ArrayList<>(); List<Integer> pseudoCritical = new ArrayList<>(); for (int i = 0; i < m; i++) { if (getMSTWeight(n, newEdges, i, -1) > minMSTWeight) { critical.add(newEdges[i][3]); } else if (getMSTWeight(n, newEdges, -1, i) == minMSTWeight) { pseudoCritical.add(newEdges[i][3]); } } List<List<Integer>> result = new ArrayList<>(); result.add(critical); result.add(pseudoCritical); return result; } private int getMSTWeight(int n, int[][] edges, int skipIndex, int forceIndex) { DSU dsu = new DSU(n); int weight = 0; int edgeCount = 0; if (forceIndex != -1) { weight += edges[forceIndex][2]; dsu.union(edges[forceIndex][0], edges[forceIndex][1]); edgeCount++; } for (int i = 0; i < edges.length; i++) { if (i == skipIndex || i == forceIndex) continue; int[] edge = edges[i]; if (dsu.union(edge[0], edge[1])) { weight += edge[2]; edgeCount++; } } return (edgeCount == n - 1 && dsu.isSingleComponent()) ? weight : Integer.MAX_VALUE; } class DSU { int[] parent; int components; public DSU(int n) { parent = new int[n]; components = n; for (int i = 0; i < n; i++) parent[i] = i; } public int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } public boolean union(int u, int v) { int rootU = find(u); int rootV = find(v); if (rootU != rootV) { parent[rootU] = rootV; components--; return true; } return false; } public boolean isSingleComponent() { return components == 1; } }}Complexity
Time
O(m² * α(n)), where `α(n)` is the inverse Ackermann function. Sorting takes `O(m log m)`. The main loop runs `m` times, with each iteration taking `O(m * α(n))` for the MST calculation.
Space
O(m + n) for storing the augmented edges and the DSU data structure.
Trade-offs
Pros
Faster than the naive brute-force approach.
Sufficiently efficient for the given problem constraints.
Relatively straightforward to implement.
Cons
The time complexity is still quadratic, which might be too slow for problems with a larger number of edges.
This approach directly follows the definitions of critical and pseudo-critical edges. It iterates through every edge and, for each one, re-calculates the Minimum Spanning Tree (MST) under different conditions: once with the edge removed (to test for criticality) and once with the edge forced into the tree (to test for pseudo-criticality).
Algorithm
- First, calculate the weight of a standard Minimum Spanning Tree (MST) for the entire graph, let's call it
min_mst_weight. This can be done using Kruskal's or Prim's algorithm. - To identify critical edges: Iterate through each edge
ein the graph. Temporarily removeeand calculate the MST of the remaining graph. If the new MST weight is greater thanmin_mst_weight, or if the graph becomes disconnected (making an MST impossible), theneis a critical edge. - To identify pseudo-critical edges: Iterate through each edge
ethat is not critical. Forceeto be part of a spanning tree by including it first. Then, complete the spanning tree using other edges with an MST algorithm. If the total weight of this new spanning tree is equal tomin_mst_weight, theneis a pseudo-critical edge. - Each MST calculation involves creating a new list of edges and sorting it, which is inefficient.
Walkthrough
The fundamental idea is to test each edge individually against the definitions. We first establish a baseline by computing the weight of an MST of the original graph. Let this be min_mst_weight.
For an edge e to be critical, its absence must make it impossible to achieve min_mst_weight. We test this by removing e and running an MST algorithm like Kruskal's on the rest of the graph. If the resulting MST weight is higher than min_mst_weight, or if the graph is no longer connected, e is critical.
For an edge e to be pseudo-critical, it must be part of some MST but not all. If we've already determined e is not critical, we check if it can be in any MST. We do this by forcing its inclusion. We start building a spanning tree with e and then run Kruskal's on the remaining edges to add n-2 more edges optimally. If the final tree's weight is exactly min_mst_weight, e is pseudo-critical.
The main drawback is the performance. For each of the m edges, we run an MST algorithm which typically involves sorting m-1 edges. This leads to a very slow, albeit straightforward, solution.
Complexity
Time
O(m² log m). Finding the initial MST costs `O(m log m)`. The main loop runs `m` times. Inside the loop, checking for criticality or pseudo-criticality involves running an MST algorithm on `O(m)` edges, which costs `O(m log m)`. This results in a total complexity of `O(m * m log m)`.
Space
O(m + n), where `m` is the number of edges and `n` is the number of vertices. This space is used to store the graph edges and the data structures for the MST algorithm (like a Disjoint Set Union).
Trade-offs
Pros
Conceptually simple and directly translates the problem definition into code.
Easy to implement if a standard MST function is available.
Cons
Very high time complexity due to repeated sorting and MST calculations.
Likely to result in a 'Time Limit Exceeded' error for larger inputs.
Solutions
Solution
class Solution {public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) { for (int i = 0; i < edges.length; ++i) { int[] e = edges[i]; int[] t = new int[4]; System.arraycopy(e, 0, t, 0, 3); t[3] = i; edges[i] = t; } Arrays.sort(edges, Comparator.comparingInt(a->a[2])); int v = 0; UnionFind uf = new UnionFind(n); for (int[] e : edges) { int f = e[0], t = e[1], w = e[2]; if (uf.union(f, t)) { v += w; } } List<List<Integer>> ans = new ArrayList<>(); for (int i = 0; i < 2; ++i) { ans.add(new ArrayList<>()); } for (int[] e : edges) { int f = e[0], t = e[1], w = e[2], i = e[3]; uf = new UnionFind(n); int k = 0; for (int[] ne : edges) { int x = ne[0], y = ne[1], z = ne[2], j = ne[3]; if (j != i && uf.union(x, y)) { k += z; } } if (uf.getN() > 1 || (uf.getN() == 1 && k > v)) { ans.get(0).add(i); continue; } uf = new UnionFind(n); uf.union(f, t); k = w; for (int[] ne : edges) { int x = ne[0], y = ne[1], z = ne[2], j = ne[3]; if (j != i && uf.union(x, y)) { k += z; } } if (k == v) { ans.get(1).add(i); } } return ans; }} class UnionFind {private int[] p;private int n;public UnionFind(int n) { p = new int[n]; this.n = n; for (int i = 0; i < n; ++i) { p[i] = i; } }public int getN() { return n; }public boolean union(int a, int b) { if (find(a) == find(b)) { return false; } p[find(a)] = find(b); --n; return true; }public int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }}class UnionFind { public: vector < int > p ; int n ; UnionFind ( int _n ) : n ( _n ) , p ( _n ) { iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { if ( find ( a ) == find ( b )) return false ; p [ find ( a )] = find ( b ); -- n ; return true ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } }; class Solution { public: vector < vector < int >> findCriticalAndPseudoCriticalEdges ( int n , vector < vector < int >>& edges ) { for ( int i = 0 ; i < edges . size (); ++ i ) edges [ i ]. push_back ( i ); sort ( edges . begin (), edges . end (), []( auto & a , auto & b ) { return a [ 2 ] < b [ 2 ]; }); int v = 0 ; UnionFind uf ( n ); for ( auto & e : edges ) { int f = e [ 0 ], t = e [ 1 ], w = e [ 2 ]; if ( uf . unite ( f , t )) v += w ; } vector < vector < int >> ans ( 2 ); for ( auto & e : edges ) { int f = e [ 0 ], t = e [ 1 ], w = e [ 2 ], i = e [ 3 ]; UnionFind ufa ( n ); int k = 0 ; for ( auto & ne : edges ) { int x = ne [ 0 ], y = ne [ 1 ], z = ne [ 2 ], j = ne [ 3 ]; if ( j != i && ufa . unite ( x , y )) k += z ; } if ( ufa . n > 1 || ( ufa . n == 1 && k > v )) { ans [ 0 ]. push_back ( i ); continue ; } UnionFind ufb ( n ); ufb . unite ( f , t ); k = w ; for ( auto & ne : edges ) { int x = ne [ 0 ], y = ne [ 1 ], z = ne [ 2 ], j = ne [ 3 ]; if ( j != i && ufb . unite ( x , y )) k += z ; } if ( k == v ) ans [ 1 ]. push_back ( i ); } return ans ; } };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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.