What is the time complexity of Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree?

The optimal solution for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree runs in O(E log E) time and uses O(E) space. The complexity comes from sorting the edges (O(E log E)) and performing union-find operations, which are nearly constant time due to path compression.

What is the brute force solution for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree?

The brute force approach for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree is Brute Force, with O(2^E * E log E) time complexity and O(E) space complexity. In the brute force approach, we can generate all possible subsets of edges to form different spanning trees and check their weights. This method is straightforward but inefficient as it explores every combination. The optimal Optimal Solution approach improves this to O(E log E).

What are the interview tips for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree?

Clearly explain your thought process and the steps you take to reach the solution. Practice implementing union-find and Kruskal's algorithm, as they are commonly used in graph problems. Be prepared to discuss the time and space complexity of your solution.

What are common mistakes when solving Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree?

Failing to correctly implement the union-find structure, leading to incorrect cycle detection. Not considering all edges when determining if they are critical or pseudo-critical.

#1489

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Hard

Union-FindGraph TheorySortingMinimum Spanning TreeStrongly Connected ComponentUnion-FindGraph TheoryMinimum Spanning Tree

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(2^E * E log E)	O(E log E)
Space	O(E)	O(E)

💡

Intuition

Time O(E log E)Space O(E)

Using Kruskal's algorithm with a union-find data structure allows us to efficiently determine the minimum spanning tree and identify critical and pseudo-critical edges without generating all subsets.

⚙️

Algorithm

4 steps

1Step 1: Sort the edges by weight.
2Step 2: Use union-find to construct the minimum spanning tree (MST) and calculate its weight.
3Step 3: For each edge, check if removing it increases the MST weight (critical edge).
4Step 4: For each edge, check if including it in the MST results in the same weight (pseudo-critical edge).

solution.py49 lines

1# Full working Python code
2class UnionFind:
3    def __init__(self, n):
4        self.parent = list(range(n))
5        self.rank = [1] * n
6    def find(self, x):
7        if self.parent[x] != x:
8            self.parent[x] = self.find(self.parent[x])
9        return self.parent[x]
10    def union(self, x, y):
11        rootX, rootY = self.find(x), self.find(y)
12        if rootX != rootY:
13            if self.rank[rootX] > self.rank[rootY]:
14                self.parent[rootY] = rootX
15            elif self.rank[rootX] < self.rank[rootY]:
16                self.parent[rootX] = rootY
17            else:
18                self.parent[rootY] = rootX
19                self.rank[rootX] += 1
20
21def kruskal(n, edges, skip_index=-1, include_index=-1):
22    uf = UnionFind(n)
23    total_weight = 0
24    edge_count = 0
25    if include_index != -1:
26        u, v, w, _ = edges[include_index]
27        uf.union(u, v)
28        total_weight += w
29        edge_count += 1
30    for i, (u, v, w, _) in enumerate(edges):
31        if i == skip_index:
32            continue
33        if uf.find(u) != uf.find(v):
34            uf.union(u, v)
35            total_weight += w
36            edge_count += 1
37    return total_weight if edge_count == n - 1 else float('inf')
38
39def findCriticalAndPseudoCriticalEdges(n, edges):
40    edges = [[u, v, w, i] for i, (u, v, w) in enumerate(edges)]
41    edges.sort(key=lambda x: x[2])
42    mst_weight = kruskal(n, edges)
43    critical, pseudo_critical = [], []
44    for i in range(len(edges)):
45        if kruskal(n, edges, skip_index=i) > mst_weight:
46            critical.append(edges[i][3])
47        elif kruskal(n, edges, include_index=i) == mst_weight:
48            pseudo_critical.append(edges[i][3])
49    return [critical, pseudo_critical]

ℹ

Complexity note: The complexity comes from sorting the edges (O(E log E)) and performing union-find operations, which are nearly constant time due to path compression.

1Understanding the difference between critical and pseudo-critical edges is essential for solving this problem effectively.
2Using union-find efficiently helps manage connected components and detect cycles while building the MST.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.