# Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree)
Canonical: https://scaleengineer.com/dsa/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Union Find](https://scaleengineer.com/algorithms/union-find), [Minimum Spanning Tree](https://scaleengineer.com/algorithms/minimum-spanning-tree)
**Data structures:** Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/image0.png)

**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:
![](https://assets.glich.co/dsa/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/image1.png)
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:**

![](https://assets.glich.co/dsa/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/image2.png)

**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 <= 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**.

# Approaches
## Brute Force with Full Recalculation
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).
**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).
**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.
### Explanation
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.
### 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 `e` in the graph. Temporarily remove `e` and calculate the MST of the remaining graph. If the new MST weight is greater than `min_mst_weight`, or if the graph becomes disconnected (making an MST impossible), then `e` is a critical edge.
- To identify **pseudo-critical edges**: Iterate through each edge `e` that is not critical. Force `e` to 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 to `min_mst_weight`, then `e` is a pseudo-critical edge.
- Each MST calculation involves creating a new list of edges and sorting it, which is inefficient.

## Optimized Brute Force with Pre-sorting
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.
**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.
**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.
### Explanation
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)`.

```java
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;
        }
    }
}
```
### 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, `critical` and `pseudoCritical`.
- Iterate through each edge `i` from `0` to `m-1`:
  - **To check for criticality**: Calculate the MST weight of the graph while ignoring edge `i`. If this weight is greater than `minMSTWeight`, add the original index of edge `i` to the `critical` list.
  - **To check for pseudo-criticality**: If edge `i` is not critical, calculate the MST weight while forcing the inclusion of edge `i`. If this weight is equal to `minMSTWeight`, add the original index of edge `i` to the `pseudoCritical` list.
- The MST calculations in the loop are done on the pre-sorted list of edges, avoiding the expensive re-sorting step.

## Optimal Approach with Union-Find and Bridge Finding
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).
**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.
**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.
### Explanation
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.
### 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`:
  1. **Find Candidates**: For each edge `(u, v)` in the block, check if its endpoints `u` and `v` are already connected in the DSU (which represents components formed by edges lighter than `w`). If `find(u) != find(v)`, this edge is a candidate for being in an MST. Collect all such candidates.
  2. **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.
  3. **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.
  4. **Identify Pseudo-Critical**: Any candidate edge that is *not* a bridge is a **pseudo-critical edge**.
  5. **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.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
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 ; } };
```

### Python

```python
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
```