⚡Flashcard Drill➔
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

  1. Compute the MST weight once as the baseline.
  2. An edge is critical if excluding it increases the MST weight (or makes the graph disconnected).
  3. An edge is pseudo-critical if forcing it into the MST does not increase the weight.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems