← Weighted Undirected Graph → Minimum Spanning Tree

Critical & Pseudo-Critical MST Edges

Hard
Solve it on LeetCode ↗

The problem

For each edge of a weighted graph decide: critical (in EVERY minimum spanning tree) or pseudo-critical (in SOME MST but not all). Return both lists of edge indices.

Stuck? Reveal hints one at a time

How to approach it

  1. 1Sort edges by weight (remembering original indices); run Kruskal for the baseline weight W.
  2. 2For each edge e: run Kruskal skipping e. If the result exceeds W or the graph cannot connect, e is critical.
  3. 3Otherwise run Kruskal with e pre-added (union its endpoints, start weight = e.w). If the total still equals W, e is pseudo-critical.
  4. 4Edges failing both tests are in no MST.

Key insight

Both tests are one Kruskal run each with a twist — "forbid this edge" or "force this edge" — comparing against the baseline weight answers membership questions exactly.

The solution

Watch out for

  • Sort a COPY that carries original indices — the answer wants indices into the input order.
  • When forcing an edge, count it toward both the weight and the used-edge tally.