Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

HARD

Description

Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [a_i, b_i, weight_i] represents a bidirectional and weighted edge between nodes a_i and b_i. 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 <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= a_i < b_i < n
1 <= weight_i <= 1000
All pairs (a_i, b_i) are distinct.

Approaches

Checkout 3 different approaches to solve Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree. Click on different approaches to view the approach and algorithm in detail.

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).

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.

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 Analysis

Time Complexity: 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 Complexity: O(m + n) to store edges, the DSU, and the temporary data structures for the component graph and bridge-finding algorithm.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Algorithms:

SortingUnion FindMinimum Spanning Tree

Data Structures:

Graph