Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1613. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

My accepted Python solution to LeetCode problem 1613, Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree, running in 534ms.

  • Difficulty: Hard
  • Python
  • Runtime 534ms
  • Memory 17.9MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 534ms, memory 17.9MB, accepted 2025-12-29.

python
class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        # Add original index to edges
        indexed_edges = [(u, v, w, i) for i, (u, v, w) in enumerate(edges)]
        indexed_edges.sort(key=lambda x: x[2])
        
        def find(parent, x):
            if parent[x] != x:
                parent[x] = find(parent, parent[x])
            return parent[x]
        
        def union(parent, rank, x, y):
            px, py = find(parent, x), find(parent, y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True
        
        def mst_weight(n, edges, include=None, exclude=None):
            parent = list(range(n))
            rank = [0] * n
            weight = 0
            count = 0
            
            if include is not None:
                u, v, w, _ = include
                union(parent, rank, u, v)
                weight += w
                count += 1
            
            for u, v, w, idx in edges:
                if exclude is not None and idx == exclude:
                    continue
                if union(parent, rank, u, v):
                    weight += w
                    count += 1
            
            return weight if count == n - 1 else float('inf')
        
        original_mst = mst_weight(n, indexed_edges)
        critical = []
        pseudo_critical = []
        
        for u, v, w, idx in indexed_edges:
            # Check if critical (excluding it increases MST weight)
            if mst_weight(n, indexed_edges, exclude=idx) > original_mst:
                critical.append(idx)
            # Check if pseudo-critical (including it doesn't increase MST weight)
            elif mst_weight(n, indexed_edges, include=(u, v, w, idx)) == original_mst:
                pseudo_critical.append(idx)
        
        return [critical, pseudo_critical]

Source