LeetCode Solutions Blog

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Difficulty: Hard

Problem Description

Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight. Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all. Note that you can return the indices of the edges in any order.

Key Insights

A critical edge is essential for the minimum spanning tree; removing it increases the total weight.
A pseudo-critical edge can be included in some valid MSTs but is not necessary for all.
The problem involves analyzing the edges in relation to the MST using graph algorithms.
Union-Find (Disjoint Set Union) is an efficient data structure for determining connected components and can help find MSTs.

Space and Time Complexity

Time Complexity: O(E log E + E * α(N)), where E is the number of edges, and α(N) is the inverse Ackermann function that grows very slowly. Space Complexity: O(N + E), where N is the number of vertices and E is the number of edges.

Solution

To solve the problem, we use Kruskal's algorithm in conjunction with the Union-Find data structure. First, we sort the edges based on their weights. We then find the MST weight using all edges. For each edge, we check if removing it increases the MST weight (to identify critical edges) and if including it yields the same MST weight (to identify pseudo-critical edges). We perform these operations using the Union-Find structure to efficiently manage connected components.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]

    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU != rootV:
            if self.rank[rootU] > self.rank[rootV]:
                self.parent[rootV] = rootU
            elif self.rank[rootU] < self.rank[rootV]:
                self.parent[rootU] = rootV
            else:
                self.parent[rootV] = rootU
                self.rank[rootU] += 1
            return True
        return False

def mst_weight(n, edges, skip_edge=None, include_edge=None):
    uf = UnionFind(n)
    total_weight = 0
    edges_used = 0

    if include_edge is not None:
        total_weight += include_edge[2] # Include the edge weight
        uf.union(include_edge[0], include_edge[1])
        edges_used += 1

    for i, (u, v, w) in enumerate(edges):
        if i == skip_edge:
            continue
        if uf.union(u, v):
            total_weight += w
            edges_used += 1
            if edges_used == n - 1:  # MST is complete
                break
    
    return total_weight if edges_used == n - 1 else float('inf')

def findCriticalAndPseudoCriticalEdges(n, edges):
    edges = [(u, v, w, i) for i, (u, v, w) in enumerate(edges)]
    edges.sort(key=lambda x: x[2])  # Sort by weights

    mst_weight_without_edge = mst_weight(n, edges)  # Weight of the MST
    critical_edges = []
    pseudo_critical_edges = []

    for i in range(len(edges)):
        if mst_weight(n, edges, skip_edge=i) > mst_weight_without_edge:
            critical_edges.append(edges[i][3])  # Edge index
        elif mst_weight(n, edges, include_edge=edges[i]) == mst_weight_without_edge:
            pseudo_critical_edges.append(edges[i][3])  # Edge index

    return [critical_edges, pseudo_critical_edges]