Find critical and pseudo critical edges in minimum spanning tree

Union-Find Graph Theory Sorting Minimum Spanning Tree Strongly Connected Component

66.4% acceptance

Feb 25, 2026

1997

170

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. 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. A pseudo-critical edge is that which can appear in some MSTs but not all.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_critical_and_pseudo_critical_edges(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = n as usize;
    let m = edges.len();
    // Add original indices and sort by weight
    let mut indexed: Vec<(i32, usize, usize, usize)> = edges.iter().enumerate()
      .map(|(i, e)| (e[2], e[0] as usize, e[1] as usize, i))
      .collect();
    indexed.sort_unstable();

    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x { parent[x] = find(parent, parent[x]); }
      parent[x]
    }
    fn union(parent: &mut Vec<usize>, rank: &mut Vec<usize>, x: usize, y: usize) -> bool {
      let (rx, ry) = (find(parent, x), find(parent, y));
      if rx == ry { return false; }
      if rank[rx] < rank[ry] { parent[rx] = ry; }
      else if rank[rx] > rank[ry] { parent[ry] = rx; }
      else { parent[ry] = rx; rank[rx] += 1; }
      true
    }

    // Kruskal's MST, optionally excluding or forcing an edge
    let mst_weight = |skip: Option<usize>, force: Option<usize>| -> i32 {
      let mut parent: Vec<usize> = (0..n).collect();
      let mut rank = vec![0usize; n];
      let mut weight = 0i32;
      let mut cnt = 0usize;
      if let Some(f) = force {
        let e = &indexed[f];
        union(&mut parent, &mut rank, e.1, e.2);
        weight += e.0;
        cnt += 1;
      }
      for (i, &(w, u, v, _)) in indexed.iter().enumerate() {
        if Some(i) == skip { continue; }
        if union(&mut parent, &mut rank, u, v) {
          weight += w;
          cnt += 1;
        }
      }
      if cnt == n - 1 { weight } else { i32::MAX }
    };

    let base = mst_weight(None, None);
    let mut critical = vec![];
    let mut pseudo = vec![];

    for i in 0..m {
      let orig_idx = indexed[i].3 as i32;
      if mst_weight(Some(i), None) > base {
        critical.push(orig_idx);
      } else if mst_weight(None, Some(i)) == base {
        pseudo.push(orig_idx);
      }
    }
    vec![critical, pseudo]
  }
}