Find Critical and Pseudo-Critical Edges in MST

Kruskal with forced include/exclude

Kruskal’s + edge classification. Deep graph understanding.

Published Apr 16, 2026

Problem

You're given a weighted undirected graph with n vertices (labeled 0..n-1) and edges[i] = [u, v, weight].

Classify every edge:

Critical — the edge is in every minimum spanning tree. Removing it strictly increases MST weight (or makes the graph disconnected).
Pseudo-critical — the edge is in at least one MST but not all.

Return [critical_indices, pseudo_critical_indices]. Each list is a list of original edge indices.

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

Edges 0 and 1 appear in every MST. Edges 2-5 appear in some MST but can be swapped with another equal-weight edge.

Input

n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]

Output

[[],[0,1,2,3]]

Explanation

All edges have weight 1 and form a 4-cycle. Any 3-edge subset is a valid MST, so none are critical but all are pseudo-critical.

Intuition

Kruskal's algorithm builds an MST by sorting edges by weight and adding any edge whose endpoints are in different components. The total weight is unique even when the tree is not.

Call the optimal weight W. For each edge e:

Force-exclude test: run Kruskal without e. If the result is not a spanning tree, or its weight exceeds W, then e is critical — the MST required it.
Force-include test: if not critical, start Kruskal with e already in the MST (union its endpoints and add its weight), then finish Kruskal. If the result has weight W, e is pseudo-critical — at least one MST contains it.

Each test is one Kruskal run in O(E · α(V)), and we do two per edge, so the total is O(E^2 · α(V)). Cheap enough for LeetCode's constraints (|edges| ≤ 200).

Approach

Brute: Compare Every MST Weight

TimeO(E^2 · α(V))

SpaceO(V + E)

Same Kruskal-twice-per-edge logic, just with an explicit standard_mst_weight baseline and minimal union-find abstraction.

struct DSU {
    parent: Vec<usize>,
    rank: Vec<usize>,
    components: usize,
}

impl DSU {
    fn new(n: usize) -> Self {
        DSU { parent: (0..n).collect(), rank: vec![0; n], components: n }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let p = self.parent[x];
            self.parent[x] = self.find(p);
        }
        self.parent[x]
    }
    fn union(&mut self, a: usize, b: usize) -> bool {
        let (ra, rb) = (self.find(a), self.find(b));
        if ra == rb { return false; }
        if self.rank[ra] < self.rank[rb] {
            self.parent[ra]= rb;
        } else if self.rank[ra] > self.rank[rb] {
            self.parent[rb] = ra;
        } else {
            self.parent[rb] = ra;
            self.rank[ra] += 1;
        }
        self.components -= 1;
        true
    }
}

impl Solution {
    pub fn find_critical_and_pseudo_critical_edges(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize;
        // Keep original index alongside each edge.
        let mut indexed: Vec<(usize, i32, i32, i32)> = edges
            .iter()
            .enumerate()
            .map(|(i, e)| (i, e[0], e[1], e[2]))
            .collect();
        indexed.sort_by_key(|&(_, _, _, w)| w);

        let standard = Self::mst_weight(n, &indexed, None, None);

        let mut critical = Vec::new();
        let mut pseudo = Vec::new();
        for idx in 0..edges.len() {
            // Force-exclude: skip this edge.
            let without = Self::mst_weight(n, &indexed, Some(idx), None);
            if without > standard {
                critical.push(idx as i32);
                continue;
            }
            // Force-include: seed DSU with this edge.
            let with = Self::mst_weight(n, &indexed, None, Some(idx));
            if with == standard {
                pseudo.push(idx as i32);
            }
        }

        vec![critical, pseudo]
    }

    // Returns i32::MAX if the MST can't span n vertices.
    fn mst_weight(
        n: usize,
        sorted: &[(usize, i32, i32, i32)],
        exclude: Option<usize>,
        include: Option<usize>,
    ) -> i32 {
        let mut dsu = DSU::new(n);
        let mut total: i32 = 0;

        if let Some(inc) = include {
            let e = sorted.iter().find(|(i, _, _, _)| *i == inc).unwrap();
            dsu.union(e.1 as usize, e.2 as usize);
            total += e.3;
        }

        for &(i, u, v, w) in sorted {
            if Some(i) == exclude || Some(i) == include { continue; }
            if dsu.union(u as usize, v as usize) {
                total += w;
            }
        }

        if dsu.components == 1 { total } else { i32::MAX }
    }
}

Rust · runnable

function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
  type Edge = { idx: number; u: number; v: number; w: number };
  const indexed: Edge[] = edges.map((e, i) => ({ idx: i, u: e[0], v: e[1], w: e[2] }));
  indexed.sort((a, b) => a.w - b.w);

  const INF = Number.POSITIVE_INFINITY;

  const mstWeight = (exclude: number | null, include: number | null): number => {
    const parent = Array.from({ length: n }, (_, i) => i);
    const rank = new Array<number>(n).fill(0);
    let components = n;
    const find = (x: number): number => {
      while (parent[x] !== x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
      }
      return x;
    };
    const union = (a: number, b: number): boolean => {
      const ra = find(a);
      const rb = find(b);
      if (ra === rb) return false;
      if (rank[ra] < rank[rb]) parent[ra]= rb;
      else if (rank[ra] > rank[rb]) parent[rb] = ra;
      else { parent[rb] = ra; rank[ra]++; }
      components--;
      return true;
    };

    let total = 0;
    if (include !== null) {
      const e = indexed.find((x) => x.idx === include)!;
      union(e.u, e.v);
      total += e.w;
    }
    for (const e of indexed) {
      if (e.idx === exclude || e.idx === include) continue;
      if (union(e.u, e.v)) total += e.w;
    }
    return components === 1 ? total : INF;
  };

  const standard = mstWeight(null, null);
  const critical: number[] = [];
  const pseudo: number[] = [];
  for (let i = 0; i < edges.length; i++) {
    if (mstWeight(i, null) > standard) {
      critical.push(i);
      continue;
    }
    if (mstWeight(null, i) === standard) {
      pseudo.push(i);
    }
  }

  return [critical, pseudo];
}

TypeScript · runnable

Kruskal with Forced Inclusion/Exclusion

TimeO(E^2 · α(V))

SpaceO(V + E)

Recommended

Same algorithm, packaged cleanly. The "brute" label is partly historical — this IS the textbook solution, but it runs two Kruskal passes per edge. An advanced approach (Tarjan's offline DFS on the Kruskal forest) hits O(E · α(V)) but is much subtler; for |E| ≤ 200 this version is both optimal-enough and pedagogically direct.

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();
        // (orig_idx, u, v, w) sorted by w — re-used across all Kruskal runs.
        let mut sorted: Vec<(usize, usize, usize, i32)> = edges
            .iter()
            .enumerate()
            .map(|(i, e)| (i, e[0] as usize, e[1] as usize, e[2]))
            .collect();
        sorted.sort_by_key(|&(_, _, _, w)| w);

        let kruskal = |exclude: i32, include: i32| -> i32 {
            let mut parent: Vec<usize> = (0..n).collect();
            let mut rank = vec![0usize; n];
            let mut components = n;
            fn find(parent: &mut [usize], mut x: usize) -> usize {
                while parent[x] != x {
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                x
            }
            let mut union = |parent: &mut Vec<usize>, rank: &mut Vec<usize>, components: &mut usize, a: usize, b: usize| -> bool {
                let ra = find(parent, a);
                let rb = find(parent, b);
                if ra == rb { return false; }
                if rank[ra] < rank[rb] {
                    parent[ra]= rb;
                } else if rank[ra] > rank[rb] {
                    parent[rb] = ra;
                } else {
                    parent[rb] = ra;
                    rank[ra] += 1;
                }
                *components -= 1;
                true
            };

            let mut total: i32 = 0;
            if include >= 0 {
                let e = sorted.iter().find(|&&(i, _, _, _)| i as i32 == include).unwrap();
                union(&mut parent, &mut rank, &mut components, e.1, e.2);
                total += e.3;
            }
            for &(i, u, v, w) in &sorted {
                if i as i32 == exclude || i as i32 == include { continue; }
                if union(&mut parent, &mut rank, &mut components, u, v) {
                    total += w;
                }
            }
            if components == 1 { total } else { i32::MAX }
        };

        let standard = kruskal(-1, -1);
        let mut critical: Vec<i32> = Vec::new();
        let mut pseudo: Vec<i32> = Vec::new();
        for i in 0..m {
            // If omitting edge i changes the MST weight (or disconnects), it's critical.
            if kruskal(i as i32, -1) > standard {
                critical.push(i as i32);
                continue;
            }
            // Otherwise, if forcing i in still hits the optimal weight, it's pseudo-critical.
            if kruskal(-1, i as i32) == standard {
                pseudo.push(i as i32);
            }
        }

        vec![critical, pseudo]
    }
}

Rust · runnable

function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
  const m = edges.length;
  type Edge = { idx: number; u: number; v: number; w: number };
  const sorted: Edge[] = edges.map((e, i) => ({ idx: i, u: e[0], v: e[1], w: e[2] }));
  sorted.sort((a, b) => a.w - b.w);

  const INF = Number.POSITIVE_INFINITY;
  const kruskal = (exclude: number, include: number): number => {
    const parent = Array.from({ length: n }, (_, i) => i);
    const rank = new Array<number>(n).fill(0);
    let components = n;
    const find = (x: number): number => {
      while (parent[x] !== x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
      }
      return x;
    };
    const union = (a: number, b: number): boolean => {
      const ra = find(a);
      const rb = find(b);
      if (ra === rb) return false;
      if (rank[ra] < rank[rb]) parent[ra]= rb;
      else if (rank[ra] > rank[rb]) parent[rb] = ra;
      else { parent[rb] = ra; rank[ra]++; }
      components--;
      return true;
    };

    let total = 0;
    if (include >= 0) {
      const e = sorted.find((x) => x.idx === include)!;
      union(e.u, e.v);
      total += e.w;
    }
    for (const e of sorted) {
      if (e.idx === exclude || e.idx === include) continue;
      if (union(e.u, e.v)) total += e.w;
    }
    return components === 1 ? total : INF;
  };

  const standard = kruskal(-1, -1);
  const critical: number[] = [];
  const pseudo: number[] = [];
  for (let i = 0; i < m; i++) {
    if (kruskal(i, -1) > standard) {
      critical.push(i);
      continue;
    }
    if (kruskal(-1, i) === standard) {
      pseudo.push(i);
    }
  }

  return [critical, pseudo];
}

TypeScript · runnable

A few correctness details:

INF for disconnection — if Kruskal with an edge excluded leaves fewer than n unified components, treat the weight as infinity. That guarantees the > standard check fires.
Force-include seeds DSU first — then iterate sorted edges, skipping the included edge on the second visit to avoid adding it twice.
Equal-weight ordering is stable for correctness — any tie-break works because the "force-include" test compares total weight, not edge identity.

Trace

Standard MST on edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]] (indices 0-6):

step	edge idx	(u,v,w)	action	components
1	0	(0,1,1)	union	4
2	1	(1,2,1)	union	3
3	2	(2,3,2)	union	2
4	3	(0,3,2)	skip (cycle)	2
5	4	(0,4,3)	union	1
6	5	(3,4,3)	skip (cycle)	1
7	6	(1,4,6)	skip (cycle)	1

Standard weight W = 1 + 1 + 2 + 3 = 7.

Exclude edge 0: remaining edges force W' = 1 + 1 + 2 + 2 + 3 = ... wait, actually without edge 0, the next lightest MST is 1 + 2 + 3 + 6 = ... — if we exclude edge (0,1,1), Kruskal picks (1,2,1), (2,3,2), (0,3,2), (0,4,3) → weight 8 > 7. Edge 0 is critical.
Exclude edge 2: Kruskal picks (0,1,1), (1,2,1), (0,3,2), (0,4,3) → weight 7 = W. So edge 2 is not critical. Force-include edge 2: weight still 7. Pseudo-critical.

Edge cases

Disconnected graph after exclusion — components > 1 at the end of Kruskal → weight is INF, flagged as critical.
All equal weights in a cycle — nothing is critical (any one can be dropped), but every edge in a valid MST is pseudo-critical.
Unique edge weight forced by connectivity — always critical. E.g., the only edge to a leaf vertex.
Empty critical or empty pseudo list — both can happen; return empty vectors.

💡

Tip

Tarjan's offline algorithm (O(E · α(V))) classifies all edges in a single pass by walking Kruskal's union-find tree and checking each non-tree edge's bridge status in the MST. It's strictly faster asymptotically, but a lot more code — skip it unless you face |E| in the millions.