Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Hard · Advanced Graphs · Explanation and code example
Kruskal's Algorithm + DFS
How it works
After building one MST, edges not in the MST create cycles when added. We use DFS to find the path in the MST between the endpoints of each non-MST edge. If any edge on this path has the same weight as the non-MST edge, both edges are pseudo-critical (they can be swapped). MST edges not identified as pseudo-critical are critical.
Steps
- Build an MST using Kruskal's algorithm, recording which edges are included and building an adjacency list for the MST.
- For each edge not in the MST:
- Use
DFSto find the unique path in the MST between its endpoints. - For each edge on this path with equal weight, mark both edges as pseudo-critical.
- Use
- Critical edges are MST edges that are not pseudo-critical.
- Return both lists.
Complexity
- Time complexity:
O(E ^ 2) - Space complexity:
O(V + E)
Where
Vis the number of vertices andEis the number of edges.
Things to watch for
Forgetting to Preserve Original Edge Indices
When sorting edges by weight for Kruskal's algorithm, the original indices get lost. You must store the original index with each edge before sorting, as the problem requires returning indices from the original edge list, not the sorted order.
Incorrect Connectivity Check After Edge Removal
When testing if an edge is critical by removing it, simply checking if the MST weight increases is insufficient. The graph may become disconnected entirely, making it impossible to form any spanning tree. Always verify that all nodes remain connected (e.g., by checking if the Union-Find structure has exactly one component).
Confusing Critical and Pseudo-Critical Edge Conditions
A critical edge must be in every MST, while a pseudo-critical edge can be in some MST but not all. The testing order matters: first check if removing the edge breaks the MST (critical), then check if forcing the edge into the MST still yields minimum weight (pseudo-critical). An edge cannot be both.
Not Resetting Union-Find for Each Edge Test
Each edge must be tested with a fresh Union-Find structure. Reusing the same Union-Find instance across multiple edge tests will carry over previous union operations, leading to incorrect connectivity states and wrong classifications.
Mishandling Edges with Equal Weights
When multiple edges have the same weight, they may be interchangeable in forming an MST. This is precisely what creates pseudo-critical edges. Failing to account for weight ties can cause edges to be incorrectly classified as critical when they are actually pseudo-critical.
Python code example
from typing import List
class UnionFind:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
if self.Size[pu] < self.Size[pv]:
pu, pv = pv, pu
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
return True
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
mst = [[] for _ in range(n)]
mstEdge = []
edge_list = [(w, u, v, i) for i, (u, v, w) in enumerate(edges)]
edge_list.sort()
uf = UnionFind(n)
for w, u, v, i in edge_list:
if uf.union(u, v):
mst[u].append((v, i))
mst[v].append((u, i))
mstEdge.append(i)
def dfs(node):
for next, ind in mst[node]:
if path and ind == path[-1]:
continue
path.append(ind)
if next == dst or dfs(next):
return True
path.pop()
return False
pseudo, mstEdge = set(), set(mstEdge)
for ind in range(len(edges)):
if ind in mstEdge:
continue
path, dst = [], edges[ind][1]
dfs(edges[ind][0])
for i in path:
if edges[i][2] == edges[ind][2]:
pseudo.add(i)
pseudo.add(ind)
return [list(mstEdge - pseudo), list(pseudo)]
C++ code example
class UnionFind {
vector<int> parent, size;
public:
UnionFind(int n) {
parent.resize(n);
size.resize(n, 1);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]);
}
return parent[node];
}
bool unionSets(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (size[pu] < size[pv]) swap(pu, pv);
size[pu] += size[pv];
parent[pv] = pu;
return true;
}
};
class Solution {
vector<vector<int>> mst;
set<int> mstEdges, pseudoCriticalEdges;
vector<int> path;
int destination;
public:
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
mst.resize(n);
vector<array<int, 4>> edgeList;
for (int i = 0; i < edges.size(); ++i) {
edgeList.push_back({edges[i][2], edges[i][0], edges[i][1], i});
}
sort(edgeList.begin(), edgeList.end());
UnionFind uf(n);
for (auto& [w, u, v, idx] : edgeList) {
if (uf.unionSets(u, v)) {
mst[u].push_back(idx);
mst[v].push_back(idx);
mstEdges.insert(idx);
}
}
for (int i = 0; i < edges.size(); ++i) {
if (mstEdges.count(i)) continue;
path.clear();
destination = edges[i][1];
if (dfs(edges[i][0], -1, edges)) {
for (int p : path) {
if (edges[p][2] == edges[i][2]) {
pseudoCriticalEdges.insert(p);
pseudoCriticalEdges.insert(i);
}
}
}
}
vector<int> critical;
for (int e : mstEdges) {
if (!pseudoCriticalEdges.count(e)) critical.push_back(e);
}
return {critical, vector<int>(pseudoCriticalEdges.begin(), pseudoCriticalEdges.end())};
}
bool dfs(int node, int parent, vector<vector<int>>& edges) {
if (node == destination) return true;
for (int& edgeIdx : mst[node]) {
if (edgeIdx == parent) continue;
path.push_back(edgeIdx);
int next = edges[edgeIdx][0] == node ? edges[edgeIdx][1] : edges[edgeIdx][0];
if (dfs(next, edgeIdx, edges)) return true;
path.pop_back();
}
return false;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.