Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Problem
Given a connected, weighted, undirected graph, find all critical and pseudo-critical edges. An edge is critical if removing it increases the MST weight (it appears in every MST). An edge is pseudo-critical if it can appear in some MST but not all. Return the two lists of original edge indices.
Compute the baseline MST weight with Kruskal. For each edge: skip it and recompute — if the weight rises (or the graph disconnects) it is critical. Otherwise force it in first and recompute — if that still yields the baseline weight it is pseudo-critical.
n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]critical = [0,1], pseudo = [2,3,4,5]def find_critical_and_pseudo(n, edges):
idx = sorted(range(len(edges)), key=lambda i: edges[i][2])
def mst(skip, force):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
weight, used = 0, 0
if force != -1:
u, v, w = edges[force]
parent[find(u)] = find(v)
weight += w; used += 1
for i in idx:
if i == skip:
continue
u, v, w = edges[i]
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv
weight += w; used += 1
return weight if used == n - 1 else float('inf')
base = mst(-1, -1)
critical, pseudo = [], []
for i in range(len(edges)):
if mst(i, -1) > base:
critical.append(i)
elif mst(-1, i) == base:
pseudo.append(i)
return [critical, pseudo]function findCriticalAndPseudo(n, edges) {
const idx = edges.map((_, i) => i).sort((a, b) => edges[a][2] - edges[b][2]);
function mst(skip, force) {
const parent = Array.from({ length: n }, (_, i) => i);
const find = x => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
let weight = 0, used = 0;
if (force !== -1) {
const [u, v, w] = edges[force];
parent[find(u)] = find(v); weight += w; used++;
}
for (const i of idx) {
if (i === skip) continue;
const [u, v, w] = edges[i];
const ru = find(u), rv = find(v);
if (ru !== rv) { parent[ru] = rv; weight += w; used++; }
}
return used === n - 1 ? weight : Infinity;
}
const base = mst(-1, -1);
const critical = [], pseudo = [];
for (let i = 0; i < edges.length; i++) {
if (mst(i, -1) > base) critical.push(i);
else if (mst(-1, i) === base) pseudo.push(i);
}
return [critical, pseudo];
}class Solution {
int[] parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
int n; int[][] edges; Integer[] idx;
int mst(int skip, int force) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int weight = 0, used = 0;
if (force != -1) {
parent[find(edges[force][0])] = find(edges[force][1]);
weight += edges[force][2]; used++;
}
for (int i : idx) {
if (i == skip) continue;
int ru = find(edges[i][0]), rv = find(edges[i][1]);
if (ru != rv) { parent[ru] = rv; weight += edges[i][2]; used++; }
}
return used == n - 1 ? weight : Integer.MAX_VALUE;
}
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
this.n = n; this.edges = edges;
idx = new Integer[edges.length];
for (int i = 0; i < idx.length; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> edges[a][2] - edges[b][2]);
int base = mst(-1, -1);
List<Integer> crit = new ArrayList<>(), pseudo = new ArrayList<>();
for (int i = 0; i < edges.length; i++) {
if (mst(i, -1) > base) crit.add(i);
else if (mst(-1, i) == base) pseudo.add(i);
}
return Arrays.asList(crit, pseudo);
}
}class Solution {
public:
vector<int> parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
int mst(int n, vector<vector<int>>& e, vector<int>& idx, int skip, int force) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
int weight = 0, used = 0;
if (force != -1) {
parent[find(e[force][0])] = find(e[force][1]);
weight += e[force][2]; used++;
}
for (int i : idx) {
if (i == skip) continue;
int ru = find(e[i][0]), rv = find(e[i][1]);
if (ru != rv) { parent[ru] = rv; weight += e[i][2]; used++; }
}
return used == n - 1 ? weight : INT_MAX;
}
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
vector<int> idx(edges.size());
for (int i = 0; i < (int)idx.size(); i++) idx[i] = i;
sort(idx.begin(), idx.end(), [&](int a, int b){ return edges[a][2] < edges[b][2]; });
int base = mst(n, edges, idx, -1, -1);
vector<int> crit, pseudo;
for (int i = 0; i < (int)edges.size(); i++) {
if (mst(n, edges, idx, i, -1) > base) crit.push_back(i);
else if (mst(n, edges, idx, -1, i) == base) pseudo.push_back(i);
}
return {crit, pseudo};
}
};Explanation
Every minimum spanning tree has the same total weight, but different edges can appear in it. We classify each edge by how it affects that baseline weight, using Kruskal's algorithm (sort edges, union endpoints if they are in different components) as our MST subroutine.
First we compute the baseline MST weight once. The helper mst(skip, force) runs Kruskal while optionally forbidding one edge (skip) or pre-adding one edge before the loop (force). If the tree fails to use n - 1 edges, the graph is disconnected and the weight is infinite.
An edge is critical if banning it makes the MST heavier (or impossible): mst(i, -1) > base. Such an edge must be in every MST, because no substitute keeps the weight at the baseline.
Otherwise we test if it is pseudo-critical: force the edge in first, then build the rest. If the result still equals base, the edge belongs to some MST: mst(-1, i) == base. Edges that are neither are in no MST.
Example: edges of weight 1 (indices 0, 1) are the only way to connect their endpoints cheaply, so they are critical. The weight-2 edges (2, 3) and weight-3 edges (4, 5) each have an equal-cost twin, so they are pseudo-critical, giving critical = [0,1], pseudo = [2,3,4,5].