Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

The key idea

Problem

You are given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between nodes from_i and to_i.

A minimum spanning tree (MST) is a subset of the graph edges that connects all the vertices together, without any 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. 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 one that can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order. The answer is [critical, pseudo_critical], where the indices refer to positions in the input edges array.

Constraints

• 2 <= n <= 100
• 1 <= edges.length <= min(200, n * (n - 1) / 2)
• edges[i].length == 3
• 0 <= fromi < toi < n
• 1 <= weighti <= 1000
• All pairs (fromi, toi) are distinct.

Examples

Complexity

Time: O(E^2 * alpha(V)) Space: O(V + E)

More Union-Find (Disjoint Set) problems

• Accounts MergeMEDIUM
• Graph Valid TreeMEDIUM
• Greatest Common Divisor TraversalHARD
• Number of Connected Components in an Undirected GraphMEDIUM
• Redundant ConnectionMEDIUM