NeetCode #652LC-1489HardAdvanced GraphsNC 250
← Back to All Problems#652 · #1489 · Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree(找到最小生成树里的关键边和伪关键边)
📌 Problem Statement & Constraints
You are given a weighted undirected graph with
n nodes and edges[i] = [u, v, w]. Return a list of two lists: the indices of the critical edges (in every MST) and the pseudo-critical edges (in some MST but not all). Constraints: 2 <= n <= 100, 1 <= edges.length <= min(200, n*(n-1)/2), 1 <= w <= 1000.💡 Core Algorithmic Approaches
- Compute the MST weight once as the baseline.
- An edge is critical if excluding it increases the MST weight (or makes the graph disconnected).
- An edge is pseudo-critical if forcing it into the MST does not increase the weight.
- Each test is one Kruskal run, giving O(E^2 log E) overall -- fine for the given limits.
💻 Benchmark Python3 Implementation
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
# (weight, u, v, original index), sorted by weight
indexed = sorted((w, u, v, i) for i, (u, v, w) in enumerate(edges))
def mst(forced: int = -1, banned: int = -1) -> float:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = 0
cnt = 0
if forced != -1: # force this edge into the tree
w, u, v, _ = indexed[forced]
parent[find(u)] = find(v)
total += w
cnt += 1
for k, (w, u, v, _) in enumerate(indexed):
if k == banned:
continue
ra, rb = find(u), find(v)
if ra != rb:
parent[ra] = rb
total += w
cnt += 1
return total if cnt == n - 1 else float("inf")
base = mst()
critical, pseudo = [], []
for k in range(len(indexed)):
if mst(banned=k) > base:
critical.append(indexed[k][3]) # removing it breaks the MST
elif mst(forced=k) == base:
pseudo.append(indexed[k][3]) # forcing it keeps the weight
return [critical, pseudo]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(E^2 log E): one Kruskal run per edge, each O(E log E).
💾 Space Complexity
O(V + E) per run.
⚠️ Interview Pitfalls & Follow-ups
- Comparing with
>=for criticality: the MST weight must strictly increase. - Forgetting the connectivity check: an excluded edge may disconnect the graph, making the weight infinite.
- Classifying an edge as both critical and pseudo-critical: criticality takes precedence, hence the
elif. - Using the sorted index instead of the original index: the output must use the original indices.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.