Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Hard Top 250
Problem Description
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] denotes a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the edges of the graph that connects all vertices without cycles and with the minimum possible total edge weight.
Find all the critical and pseudo-critical edges in the minimum spanning tree (MST) of the given graph.
- A critical edge is an edge whose deletion from the graph would cause the MST weight to increase.
- A pseudo-critical edge is that which can appear in some MSTs but not all. If we force this edge to be in the MST, the minimum weight does not increase.
Return two lists: the first list contains the indices of critical edges, and the second list contains the indices of pseudo-critical edges. You can return the indices in any order.
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]]
Constraints
2 ≤ n ≤ 1001 ≤ edges.length ≤ min(200, n * (n - 1) / 2)edges[i].length == 30 ≤ ai, bi < nai != bi1 ≤ weighti ≤ 1000- All weights are positive.
Kruskal’s Deletion and Insertion Checks
First, calculate the baseline MST weight mstWeight using Kruskal’s algorithm (sort edges by weight, use Union-Find to select edges without cycle).
Because edges.length ≤ 200, we can evaluate each edge i individually:
- Is it Critical?
- Temporarily block edge
ifrom being used. - Run Kruskal’s. If the resulting MST weight is greater than
mstWeight(or the graph becomes disconnected), edgeiis critical.
- Temporarily block edge
- Is it Pseudo-Critical?
- If edge
iis not critical, we check if it is pseudo-critical by forcing it to be selected as the very first edge of the MST. - Run Kruskal’s. If the resulting MST weight equals
mstWeight, edgeiis pseudo-critical.
- If edge
Keep track of the original index of each edge, because Kruskal’s requires sorting by weight.
Solution: Kruskal’s Force & Block
import java.util.*;
class Solution {
class UnionFind {
int[] parent;
int count;
UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
count = n;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px != py) {
parent[px] = py;
count--;
return true;
}
return false;
}
}
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
int m = edges.length;
int[][] newEdges = new int[m][4]; // [u, v, weight, originalIndex]
for (int i = 0; i < m; i++) {
newEdges[i][0] = edges[i][0];
newEdges[i][1] = edges[i][1];
newEdges[i][2] = edges[i][2];
newEdges[i][3] = i;
}
Arrays.sort(newEdges, (a, b) -> Integer.compare(a[2], b[2]));
// Find standard MST weight
int mstWeight = buildMst(n, newEdges, -1, -1);
List<Integer> critical = new ArrayList<>();
List<Integer> pseudo = new ArrayList<>();
for (int i = 0; i < m; i++) {
// check if critical (blocking it increases MST weight)
int weightWithout = buildMst(n, newEdges, i, -1);
if (weightWithout > mstWeight) {
critical.add(i);
} else {
// check if pseudo-critical (forcing it keeps MST weight same)
int weightWith = buildMst(n, newEdges, -1, i);
if (weightWith == mstWeight) {
pseudo.add(i);
}
}
}
return List.of(critical, pseudo);
}
private int buildMst(int n, int[][] edges, int blockIdx, int forceIdx) {
UnionFind uf = new UnionFind(n);
int weight = 0;
if (forceIdx != -1) {
// find the forced edge and union it first
for (int[] edge : edges) {
if (edge[3] == forceIdx) {
uf.union(edge[0], edge[1]);
weight += edge[2];
break;
}
}
}
for (int[] edge : edges) {
if (edge[3] == blockIdx || edge[3] == forceIdx) continue;
if (uf.union(edge[0], edge[1])) {
weight += edge[2];
}
}
return uf.count == 1 ? weight : Integer.MAX_VALUE;
}
}class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.count = 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, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
self.count -= 1
return True
return False
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list[list[int]]) -> list[list[int]]:
m = len(edges)
# [u, v, weight, original_index]
new_edges = [[u, v, w, i] for i, (u, v, w) in enumerate(edges)]
new_edges.sort(key=lambda x: x[2])
def build_mst(block_idx, force_idx):
uf = UnionFind(n)
weight = 0
if force_idx != -1:
for u, v, w, idx in new_edges:
if idx == force_idx:
uf.union(u, v)
weight += w
break
for u, v, w, idx in new_edges:
if idx == block_idx or idx == force_idx:
continue
if uf.union(u, v):
weight += w
return weight if uf.count == 1 else float('inf')
# baseline MST weight
mst_weight = build_mst(-1, -1)
critical = []
pseudo = []
for i in range(m):
# if blocking it increases MST weight, it is critical
if build_mst(i, -1) > mst_weight:
critical.append(i)
# else if forcing it preserves the MST weight, it is pseudo-critical
elif build_mst(-1, i) == mst_weight:
pseudo.append(i)
return [critical, pseudo]#include <vector>
#include <algorithm>
#include <numeric>
class Solution {
struct UnionFind {
std::vector<int> parent;
int count;
UnionFind(int n) : count(n) {
parent.resize(n);
std::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 x, int y) {
int px = find(x), py = find(y);
if (px != py) {
parent[px] = py;
count--;
return true;
}
return false;
}
};
int buildMst(int n, const std::vector<std::vector<int>>& edges, int blockIdx, int forceIdx) {
UnionFind uf(n);
int weight = 0;
if (forceIdx != -1) {
for (const auto& edge : edges) {
if (edge[3] == forceIdx) {
uf.unite(edge[0], edge[1]);
weight += edge[2];
break;
}
}
}
for (const auto& edge : edges) {
if (edge[3] == blockIdx || edge[3] == forceIdx) continue;
if (uf.unite(edge[0], edge[1])) {
weight += edge[2];
}
}
return uf.count == 1 ? weight : 1e9;
}
public:
std::vector<std::vector<int>> findCriticalAndPseudoCriticalEdges(int n, std::vector<std::vector<int>>& edges) {
int m = edges.size();
std::vector<std::vector<int>> newEdges(m, std::vector<int>(4));
for (int i = 0; i < m; i++) {
newEdges[i] = {edges[i][0], edges[i][1], edges[i][2], i};
}
std::sort(newEdges.begin(), newEdges.end(), [](const auto& a, const auto& b) {
return a[2] < b[2];
});
int mstWeight = buildMst(n, newEdges, -1, -1);
std::vector<int> critical, pseudo;
for (int i = 0; i < m; i++) {
if (buildMst(n, newEdges, i, -1) > mstWeight) {
critical.push_back(i);
} else if (buildMst(n, newEdges, -1, i) == mstWeight) {
pseudo.push_back(i);
}
}
return {critical, pseudo};
}
};Complexity Analysis:
- Time Complexity: O(E² * alpha(V)) where E is the number of edges. We run Kruskal’s O(E) times, and each Kruskal’s run is O(E * alpha(V)) (the edges are already sorted, so we don’t need to re-sort them inside the loop).
- Space Complexity: O(V + E) to store the graph structures and union-find arrays.