Given a connected weighted graph with n vertices and edges[i] = (u, v, w), return two lists of edge indexes: the critical edges, which appear in every minimum spanning tree, and the pseudo-critical edges, which appear in some but not all.
Before you code
Compute the MST weight once. How does the minimum change if an edge is removed from the graph, and what does it mean if forcing an edge into the tree still reaches the same minimum?
Hints
- Sort the edge indexes by weight once, keeping each edge's original index.
- Write a Kruskal that can skip one edge, or start with one edge already unioned and counted.
- An edge is critical if skipping it raises the weight or leaves the graph disconnected.
- Otherwise, it is pseudo-critical if forcing it in first still gives the minimum weight.
Production & complexity notes
When solving Find critical and pseudo-critical edges in a minimum spanning tree on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Kruskal's algorithm to reinforce the underlying pattern.
What it practices
Kruskal's algorithm and the role of ties, from Kruskal's algorithm.