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.
Example 1:
Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]] Output: [[0,1],[2,3,4,5]] Explanation: The figure above describes the graph. The following figure shows all the possible MSTs:Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output. The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.
Example 2:
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]] Output: [[],[0,1,2,3]] Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
Constraints:
2 <= n <= 1001 <= edges.length <= min(200, n * (n - 1) / 2)edges[i].length == 30 <= ai < bi < n1 <= weighti <= 1000(ai, bi) are distinct.This approach involves using Kruskal's algorithm to find the Minimum Spanning Tree. First, sort all edges by weight. Then, use a Union-Find data structure to maintain and check connectivity of the nodes as edges are added to the MST. Critical edges are those whose exclusion from the MST will increase its total weight, whereas pseudo-critical edges are those that can be in any MST when forced to be present.
This solution uses Kruskal's algorithm for MST construction. We first sort edges by weight, then use a Union-Find data structure to track connected components as we build the MST. Each edge is checked to see if its exclusion increases the MST weight, which determines if it's critical. For pseudo-critical edges, we include them initially and check if they can form an MST of the same weight. The complexity involves sorting and iterating over the edges.
C++
The time complexity is O(E log E), where E is the number of edges, mainly due to sorting edges. Space complexity is O(V), where V is the number of vertices, due to the Union-Find structure.
This approach leverages Kruskal's algorithm to build MSTs while testing each edge's criticality and pseudo-criticality. We initially use Kruskal's algorithm to determine the MST and its weight without any edge removal. We then experiment with excluding and mandatorily including each edge to ascertain its nature: critical or pseudo-critical.
Steps:
This Python solution employs a Union-Find data structure for the union and find operations required in Kruskal's algorithm. The function `kruskal()` is defined to calculate the MST's weight, optionally excluding or mandatorily including certain edges. Initially, we compute the MST's weight without excluding any edge. Thereafter, each edge is tested for criticality by checking if excluding it increases the MST's weight. For pseudo-critical checking, we ensure the edge is included first and verify if the MST's weight remains unchanged. This solution efficiently identifies the critical and pseudo-critical edges.
JavaScript
Time Complexity: O(E^2 * log(E)) where E is the number of edges, due to sorting and constructing MST for each edge.
Space Complexity: O(E + V) where E is the number of edges and V is the number of vertices used for storing edges and union-find data structure.
This approach focuses on constructing subsets of edges that definitely belong or don't belong in the MST. By manipulating combinations of edges and recalculating the MST weight, this approach checks the necessity of each edge.
Steps:
This C++ solution effectively uses the Union-Find data structure for Kruskal's algorithm to determine edge connectivity. It manages edge inclusion/exclusion flexibly, ensuring optimal MST weights are computed to ascertain the critical or pseudo-critical nature of edges. Comparison of MST weight with and without specific edges indicates their status. This solution demonstrates high proficiency in handling complex graph structures using classical algorithms.
Java
Time Complexity: O(E^2 * log(E)) due to sorting edges and iterating for each edge's condition.
Space Complexity: O(E + V) for storing edges and union-find structure during operations.
| Approach | Complexity |
|---|---|
| Using Kruskal's Algorithm and Union-Find | The time complexity is O(E log E), where E is the number of edges, mainly due to sorting edges. Space complexity is O(V), where V is the number of vertices, due to the Union-Find structure. |
| Approach 1: Kruskal's Algorithm with Edge Exclusion/Inclusion | Time Complexity: O(E^2 * log(E)) where E is the number of edges, due to sorting and constructing MST for each edge. Space Complexity: O(E + V) where E is the number of edges and V is the number of vertices used for storing edges and union-find data structure. |
| Approach 2: Kruskal's Algorithm with Subset Construction | Time Complexity: O(E^2 * log(E)) due to sorting edges and iterating for each edge's condition. Space Complexity: O(E + V) for storing edges and union-find structure during operations. |
Find Critical and Pseudo Critical Edges in Minimum Spanning Tree - Leetcode 1489 - Python • NeetCodeIO • 11,665 views views
Watch 9 more video solutions →Practice Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor