Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
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 MST:
- A critical edge is an edge whose deletion from the graph would cause the MST weight to increase or make it impossible to form a spanning tree.
- A pseudo-critical edge is an edge that can appear in some MSTs but not all.
Return a list of two lists: the first containing indices of all critical edges, and the second containing indices of all pseudo-critical edges. Indices refer to the original positions in the input edges array.
Examples
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 MST has total weight 7. Edges 0 ([0,1] weight 1) and 1 ([1,2] weight 1) appear in every possible MST — removing either one forces a heavier spanning tree. These are critical.
Edges 2, 3, 4, and 5 can each appear in some valid MSTs but not all. For example, edge 2 ([2,3] weight 2) can be swapped with edge 3 ([0,3] weight 2) in the MST since both connect the same components at the same cost. These are pseudo-critical.
Example 2
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: All 4 edges have equal weight (1). Any 3 of the 4 edges form a valid MST with weight 3. Since no single edge appears in ALL MSTs (each MST leaves out exactly one edge), there are no critical edges. But every edge appears in at least one MST, so 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.
Editorial
Brute Force
Intuition
The most direct way to classify edges is to find every possible MST and then check which edges appear in all of them, some of them, or none.
A spanning tree of a graph with n vertices uses exactly n - 1 edges. So we enumerate all possible ways to choose n - 1 edges from the total E edges. For each combination, we check: does it form a valid spanning tree (connects all nodes, no cycles)? If yes, what is its total weight? Among all valid spanning trees, those with the minimum total weight are MSTs.
Once we have the complete list of MSTs, classifying edges is straightforward:
- An edge that appears in every MST is critical.
- An edge that appears in at least one MST but not all is pseudo-critical.
- An edge that appears in no MST is neither.
Step-by-Step Explanation
Let's trace through Example 2: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]].
We need to pick n - 1 = 3 edges from 4 total. There are C(4,3) = 4 combinations.
Step 1: Enumerate all combinations of 3 edges:
- Combo {0,1,2}: edges [0,1], [1,2], [2,3]
- Combo {0,1,3}: edges [0,1], [1,2], [0,3]
- Combo {0,2,3}: edges [0,1], [2,3], [0,3]
- Combo {1,2,3}: edges [1,2], [2,3], [0,3]
Step 2: Check each combo for validity (spanning tree):
- {0,1,2}: Union 0-1, 1-2, 2-3. All 4 nodes connected, no cycles. Weight = 3. ✓ Valid spanning tree.
- {0,1,3}: Union 0-1, 1-2, 0-3. All connected. Weight = 3. ✓
- {0,2,3}: Union 0-1, 2-3, 0-3. All connected. Weight = 3. ✓
- {1,2,3}: Union 1-2, 2-3, 0-3. All connected. Weight = 3. ✓
Step 3: All 4 combinations are valid spanning trees with weight 3 (minimum). So there are 4 MSTs.
Step 4: Count edge appearances across all MSTs:
- Edge 0 appears in MSTs {0,1,2}, {0,1,3}, {0,2,3} → 3 out of 4
- Edge 1 appears in MSTs {0,1,2}, {0,1,3}, {1,2,3} → 3 out of 4
- Edge 2 appears in MSTs {0,1,2}, {0,2,3}, {1,2,3} → 3 out of 4
- Edge 3 appears in MSTs {0,1,3}, {0,2,3}, {1,2,3} → 3 out of 4
Step 5: Classify edges:
- No edge appears in ALL 4 MSTs → no critical edges.
- Every edge appears in at least 1 MST → all are pseudo-critical.
Result: Critical = [], Pseudo-critical = [0, 1, 2, 3].
Algorithm
- Generate all combinations of n - 1 edges from the E total edges
- For each combination:
- Use Union-Find to check if it forms a valid spanning tree (all nodes connected, no cycles)
- If valid, record its total weight
- Find the minimum weight among all valid spanning trees (this is the MST weight)
- Collect all valid spanning trees with this minimum weight — these are the MSTs
- For each edge index i from 0 to E - 1:
- If i appears in ALL MSTs → critical
- If i appears in SOME but not all MSTs → pseudo-critical
- Return [critical_list, pseudo_critical_list]
Code
class Solution {
public:
int findRoot(vector<int>& parent, int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
int E = edges.size();
int minWeight = INT_MAX;
vector<set<int>> allMsts;
// Generate all combinations of n-1 edges
vector<int> combo;
function<void(int)> generate = [&](int start) {
if ((int)combo.size() == n - 1) {
vector<int> par(n);
iota(par.begin(), par.end(), 0);
int weight = 0;
bool valid = true;
for (int idx : combo) {
int ru = findRoot(par, edges[idx][0]);
int rv = findRoot(par, edges[idx][1]);
if (ru == rv) { valid = false; break; }
par[ru] = rv;
weight += edges[idx][2];
}
if (valid) {
int root = findRoot(par, 0);
for (int i = 1; i < n; i++)
if (findRoot(par, i) != root) { valid = false; break; }
}
if (valid) {
if (weight < minWeight) {
minWeight = weight;
allMsts = {set<int>(combo.begin(), combo.end())};
} else if (weight == minWeight) {
allMsts.push_back(set<int>(combo.begin(), combo.end()));
}
}
return;
}
for (int i = start; i < E; i++) {
combo.push_back(i);
generate(i + 1);
combo.pop_back();
}
};
generate(0);
vector<int> critical, pseudo;
for (int i = 0; i < E; i++) {
bool inAll = true, inAny = false;
for (auto& mst : allMsts) {
if (mst.count(i)) inAny = true;
else inAll = false;
}
if (inAll && !allMsts.empty()) critical.push_back(i);
else if (inAny) pseudo.push_back(i);
}
return {critical, pseudo};
}
};from itertools import combinations
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list[list[int]]) -> list[list[int]]:
E = len(edges)
min_weight = float('inf')
all_msts = []
for combo in combinations(range(E), n - 1):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
weight, valid = 0, True
for idx in combo:
u, v, w = edges[idx]
ru, rv = find(u), find(v)
if ru == rv:
valid = False
break
parent[ru] = rv
weight += w
if valid and all(find(i) == find(0) for i in range(n)):
if weight < min_weight:
min_weight = weight
all_msts = [set(combo)]
elif weight == min_weight:
all_msts.append(set(combo))
critical, pseudo = [], []
for i in range(E):
in_all = all(i in mst for mst in all_msts)
in_any = any(i in mst for mst in all_msts)
if in_all:
critical.append(i)
elif in_any:
pseudo.append(i)
return [critical, pseudo]class Solution {
int find(int[] parent, int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
int E = edges.length;
int[] minWeight = {Integer.MAX_VALUE};
List<Set<Integer>> allMsts = new ArrayList<>();
List<Integer> combo = new ArrayList<>();
generateCombos(edges, n, E, 0, combo, minWeight, allMsts);
List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
for (int i = 0; i < E; i++) {
boolean inAll = true, inAny = false;
for (Set<Integer> mst : allMsts) {
if (mst.contains(i)) inAny = true;
else inAll = false;
}
if (inAll && !allMsts.isEmpty()) critical.add(i);
else if (inAny) pseudo.add(i);
}
return Arrays.asList(critical, pseudo);
}
void generateCombos(int[][] edges, int n, int E, int start,
List<Integer> combo, int[] minWeight, List<Set<Integer>> allMsts) {
if (combo.size() == n - 1) {
int[] par = new int[n];
for (int i = 0; i < n; i++) par[i] = i;
int weight = 0;
boolean valid = true;
for (int idx : combo) {
int ru = find(par, edges[idx][0]), rv = find(par, edges[idx][1]);
if (ru == rv) { valid = false; break; }
par[ru] = rv;
weight += edges[idx][2];
}
if (valid) {
int root = find(par, 0);
for (int i = 1; i < n; i++)
if (find(par, i) != root) { valid = false; break; }
}
if (valid) {
if (weight < minWeight[0]) {
minWeight[0] = weight;
allMsts.clear();
allMsts.add(new HashSet<>(combo));
} else if (weight == minWeight[0]) {
allMsts.add(new HashSet<>(combo));
}
}
return;
}
for (int i = start; i < E; i++) {
combo.add(i);
generateCombos(edges, n, E, i + 1, combo, minWeight, allMsts);
combo.remove(combo.size() - 1);
}
}
}Complexity Analysis
Time Complexity: O(C(E, n-1) × n)
We generate all combinations of n - 1 edges from E edges. The number of combinations is C(E, n-1), which can be exponential. For each combination, we verify connectivity and compute weight using Union-Find in O(n × α(n)) ≈ O(n). Final classification iterates over E edges × number of MSTs.
With constraints E ≤ 200 and n ≤ 100, C(200, 99) is astronomically large, making this approach infeasible for large inputs.
Space Complexity: O(C(E, n-1) + n)
We store all MSTs (potentially exponentially many) plus the Union-Find parent array of size n.
Why This Approach Is Not Efficient
The brute force generates all C(E, n-1) combinations of edges, which grows exponentially. With E = 200 and n = 100, this means C(200, 99) combinations — a number with over 50 digits. No computer can enumerate this many possibilities.
The fundamental problem is that we are generating every possible spanning tree, when we really only need to answer one question per edge: "Is this edge critical, pseudo-critical, or neither?"
Key insight: we do not need to find ALL MSTs. Instead, we can test each edge individually using two targeted experiments:
- Exclude the edge and see if the MST weight increases (tests for critical).
- Force-include the edge and see if the MST weight stays the same (tests for pseudo-critical).
Each experiment builds just ONE MST using Kruskal's algorithm, which is very fast. Running two experiments per edge gives O(E) MST constructions total — far better than enumerating all possible spanning trees.
Optimal Approach - Kruskal's with Edge Testing
Intuition
Instead of finding all MSTs, we classify each edge using two clever tests built on Kruskal's MST algorithm and Union-Find.
First, compute the baseline MST weight W using standard Kruskal's. Then for each edge:
Test 1 — Is it critical? Remove this edge from the graph entirely, and rebuild the MST with Kruskal's. If the new MST weight is greater than W, or if the graph becomes disconnected (impossible to span all nodes), this edge is critical — it was holding the MST together at minimal cost, and no substitute exists at the same price.
Test 2 — Is it pseudo-critical? If the edge is not critical, force it into the MST by pre-unioning its endpoints before running Kruskal's on the remaining edges. If the resulting total weight equals W, this edge can participate in at least one valid MST — it is pseudo-critical. If forcing it raises the weight above W, it was never part of any MST.
The beauty of this approach is that we only need to run Kruskal's (which is fast) a constant number of times per edge — no need to enumerate all MSTs.
Step-by-Step Explanation
Let's trace through Example 1: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]].
Step 1: Sort edges by weight (append original indices first):
- [0,1,1,idx0], [1,2,1,idx1], [2,3,2,idx2], [0,3,2,idx3], [0,4,3,idx4], [3,4,3,idx5], [1,4,6,idx6]
Step 2: Build MST using Kruskal's:
- Edge [0,1,w=1]: Union 0-1. Weight=1. Components: {0,1},{2},{3},{4}.
- Edge [1,2,w=1]: Union 1-2. Weight=2. Components: {0,1,2},{3},{4}.
- Edge [2,3,w=2]: Union 2-3. Weight=4. Components: {0,1,2,3},{4}.
- Edge [0,3,w=2]: 0 and 3 already connected. Skip.
- Edge [0,4,w=3]: Union 0-4. Weight=7. All connected. MST complete!
- MST weight W = 7.
Step 3: Test edge 0 [0-1, weight 1] — EXCLUDE and rebuild:
- Without edge 0: build MST from edges 1,2,3,4,5,6.
- Add [1,2,w=1], [2,3,w=2], [0,3,w=2], [0,4,w=3]. Weight = 8.
- 8 > 7 → MST weight increased. Edge 0 is CRITICAL.
Step 4: Test edge 1 [1-2, weight 1] — EXCLUDE and rebuild:
- Without edge 1: build MST from edges 0,2,3,4,5,6.
- Add [0,1,w=1], [2,3,w=2], [0,3,w=2], [0,4,w=3]. Weight = 8.
- 8 > 7 → Edge 1 is CRITICAL.
Step 5: Test edge 2 [2-3, weight 2] — EXCLUDE and rebuild:
- Without edge 2: build MST from edges 0,1,3,4,5,6.
- Add [0,1,w=1], [1,2,w=1], [0,3,w=2], [0,4,w=3]. Weight = 7.
- 7 = 7 → NOT critical. Proceed to Test 2.
Step 6: Test edge 2 — FORCE-INCLUDE and rebuild:
- Pre-union 2-3, weight = 2. Build rest: add [0,1,w=1], [1,2,w=1], [0,4,w=3]. Total = 7.
- 7 = 7 → Edge 2 is PSEUDO-CRITICAL.
Step 7: Test edges 3, 4, 5 similarly — all are pseudo-critical (excluding any yields weight 7, force-including any yields weight 7).
Step 8: Test edge 6 [1-4, weight 6] — EXCLUDE: weight = 7 (not critical). FORCE-INCLUDE: pre-union 1-4, add [0,1,w=1], [1,2,w=1], [2,3,w=2]. Total = 10 > 7. NEITHER.
Result: Critical = [0, 1], Pseudo-critical = [2, 3, 4, 5].
Kruskal's with Edge Testing — Building MST and Classifying Edges — Watch how we first build the MST using Kruskal's algorithm, then test individual edges by exclusion (critical test) and forced inclusion (pseudo-critical test).
Algorithm
- Append original index to each edge, then sort edges by weight
- Build the baseline MST using Kruskal's algorithm with Union-Find. Record MST weight W
- For each edge (u, v, w, original_idx):
- Critical test: Create fresh Union-Find. Build MST excluding this edge. If graph disconnects (components > 1) or weight > W, mark as critical and move to next edge.
- Pseudo-critical test: Create fresh Union-Find. Force union(u, v) first, add weight w. Build rest of MST from remaining edges. If total weight == W, mark as pseudo-critical.
- Return [critical_edges, pseudo_critical_edges]
Code
class UnionFind {
public:
vector<int> parent;
int components;
UnionFind(int n) : parent(n), components(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
bool unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
parent[ra] = rb;
components--;
return true;
}
};
class Solution {
public:
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
int E = edges.size();
for (int i = 0; i < E; i++) edges[i].push_back(i);
sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
return a[2] < b[2];
});
UnionFind uf(n);
int mstWeight = 0;
for (auto& e : edges)
if (uf.unite(e[0], e[1])) mstWeight += e[2];
vector<int> critical, pseudo;
for (auto& e : edges) {
int u = e[0], v = e[1], w = e[2], idx = e[3];
UnionFind ufEx(n);
int wEx = 0;
for (auto& o : edges)
if (o[3] != idx && ufEx.unite(o[0], o[1])) wEx += o[2];
if (ufEx.components > 1 || wEx > mstWeight) {
critical.push_back(idx);
continue;
}
UnionFind ufIn(n);
ufIn.unite(u, v);
int wIn = w;
for (auto& o : edges)
if (o[3] != idx && ufIn.unite(o[0], o[1])) wIn += o[2];
if (wIn == mstWeight) pseudo.push_back(idx);
}
return {critical, pseudo};
}
};class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
self.parent[ra] = rb
self.components -= 1
return True
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)
mst_weight = sum(w for u, v, w, _ in edges if uf.union(u, v))
critical, pseudo = [], []
for u, v, w, idx in edges:
uf_ex = UnionFind(n)
w_ex = sum(ww for uu, vv, ww, ii in edges if ii != idx and uf_ex.union(uu, vv))
if uf_ex.components > 1 or w_ex > mst_weight:
critical.append(idx)
continue
uf_in = UnionFind(n)
uf_in.union(u, v)
w_in = w + sum(ww for uu, vv, ww, ii in edges if ii != idx and uf_in.union(uu, vv))
if w_in == mst_weight:
pseudo.append(idx)
return [critical, pseudo]class Solution {
int[] parent;
int components;
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
parent[ra] = rb;
components--;
return true;
}
void init(int n) {
parent = new int[n];
components = n;
for (int i = 0; i < n; i++) parent[i] = i;
}
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
int E = edges.length;
int[][] indexed = new int[E][4];
for (int i = 0; i < E; i++)
indexed[i] = new int[]{edges[i][0], edges[i][1], edges[i][2], i};
Arrays.sort(indexed, (a, b) -> a[2] - b[2]);
init(n);
int mstWeight = 0;
for (int[] e : indexed)
if (union(e[0], e[1])) mstWeight += e[2];
List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
for (int[] e : indexed) {
int u = e[0], v = e[1], w = e[2], idx = e[3];
init(n);
int wEx = 0;
for (int[] o : indexed)
if (o[3] != idx && union(o[0], o[1])) wEx += o[2];
if (components > 1 || wEx > mstWeight) {
critical.add(idx);
continue;
}
init(n);
union(u, v);
int wIn = w;
for (int[] o : indexed)
if (o[3] != idx && union(o[0], o[1])) wIn += o[2];
if (wIn == mstWeight) pseudo.add(idx);
}
return Arrays.asList(critical, pseudo);
}
}Complexity Analysis
Time Complexity: O(E² × α(V))
Sorting edges takes O(E log E). Building the initial MST takes O(E × α(V)). For each of the E edges, we run two MST constructions (exclude test and include test), each processing all E edges with Union-Find operations. Total: O(E × E × α(V)) = O(E² × α(V)).
Since α(V) is the inverse Ackermann function — which grows so slowly it is effectively constant for any practical input — the time complexity simplifies to O(E²). With E ≤ 200, this means at most 200 × 200 = 40,000 MST edge-processing steps, which runs in milliseconds.
Space Complexity: O(V + E)
The Union-Find structure uses O(V) space. We store the modified edges array with indices using O(E) space. Only one Union-Find instance exists at a time (we create fresh ones for each test). Result lists use at most O(E) space. Total: O(V + E).