LeetCode Solutions Blog

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Number: 1613

Difficulty: Hard

Paid? No

Problem Description

Given a weighted undirected connected graph with n vertices (labeled from 0 to n - 1) and an edge list, determine all critical and pseudo-critical edges in its Minimum Spanning Tree (MST). A critical edge is one whose removal increases the MST's total weight, while a pseudo-critical edge is one that can appear in some MSTs but not all.

Key Insights

Use Kruskal's algorithm to compute the MST.
Sort the edges by weight and use Union-Find to efficiently detect cycles.
Compute the baseline MST weight.
For each edge, test if excluding it increases the MST weight (critical edge).
For each edge, test if forcing its inclusion can still produce an MST with the same weight (pseudo-critical edge).

Space and Time Complexity

Time Complexity: O(E^2 * α(N)) where E is the number of edges and α is the inverse Ackermann function. Space Complexity: O(N + E) for the Union-Find data structure and edge storage.

Solution

The solution uses Kruskal's algorithm along with a Union-Find (Disjoint Set Union) data structure:

Compute the baseline MST weight by sorting the edges and applying Kruskal’s algorithm.
For every edge:
- To check if it is critical, recompute the MST without the edge. If the resulting weight increases or the MST cannot be formed, the edge is critical.
- To check if it is pseudo-critical, force the inclusion of the edge and then compute the MST. If the resulting total weight equals the baseline MST weight, the edge is pseudo-critical. This requires careful manipulation of the Union-Find structure and multiple MST computations.

Code Solutions

# Python solution with detailed comments

class UnionFind:
    def __init__(self, n):
        # Each node is initially its own parent
        self.parent = list(range(n))
        # Rank for union-by-rank optimization
        self.rank = [0] * n

    def find(self, x):
        # Path compression optimization
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union two sets; return True if they were separate
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return False
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        else:
            self.parent[yr] = xr
            self.rank[xr] += 1
        return True

def buildMST(n, edges, skip_edge=None, force_edge=None):
    uf = UnionFind(n)
    weight = 0
    count = 0
    # If force_edge is provided, include it prior to processing other edges
    if force_edge is not None:
        u, v, w, idx = force_edge
        if uf.union(u, v):
            weight += w
            count += 1
    # Process each edge in order of increasing weight
    for u, v, w, idx in edges:
        if skip_edge is not None and idx == skip_edge:
            continue
        if uf.union(u, v):
            weight += w
            count += 1
        if count == n - 1:
            break
    return weight if count == n - 1 else float('inf')

def findCriticalAndPseudoCriticalEdges(n, edges_input):
    edges = []
    # Append original indices to edges
    for idx, (u, v, w) in enumerate(edges_input):
        edges.append((u, v, w, idx))
    edges.sort(key=lambda x: x[2])
    original_weight = buildMST(n, edges)
    critical = []
    pseudo_critical = []
    # Check each edge
    for u, v, w, idx in edges:
        # Exclude the edge and compute MST weight
        if buildMST(n, edges, skip_edge=idx) > original_weight:
            critical.append(idx)
        else:
            # Force include this edge and compute MST weight
            if buildMST(n, edges, force_edge=(u, v, w, idx)) == original_weight:
                pseudo_critical.append(idx)
    return [critical, pseudo_critical]

# Example usage:
if __name__ == "__main__":
    n = 5
    edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
    result = findCriticalAndPseudoCriticalEdges(n, edges)
    print(result)