Find Critical And Pseudo Critical Edges In Minimum Spanning Tree - Leetcode Solution

Problem Statement:

Given a weighted undirected connected graph with n vertices. You are given the edge list edges, where edges[i] = [ui, vi, weighti] represents a bidirectional edge between nodes ui and vi with weight weighti.

A minimum spanning tree (MST) is a subset of the edges of the graph that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the minimum spanning tree (MST) of the given graph. 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 not critical, but its inclusion in any MST is mandatory.

you need to return a 2D list of size (E, 2) where E is the total number of edges in the graph. The first column of the list represents the critical edges, and the second column represents the pseudo-critical edges. The order of the edges in the output does not matter.

Constraints: -> 2 <= n <= 100 -> 1 <= edges.length <= min(200, n * (n - 1) / 2) -> edges[i].length == 3 -> 0 <= ui, vi < n -> ui != vi -> 1 <= weighti <= 1000 -> All pairs (ui, vi) are distinct.

Solution:

First, we need to generate the Minimum Spanning Tree using Kruskal's algorithm. The steps are:

1. Sort the edges based on their weight in ascending order.
2. Initialize the number of sets as the number of vertices.
3. Traverse the sorted edges list and join the sets of corresponding vertices, if joined add edges to MST, until the number of sets becomes one(no cycles).
4. Iterate the edges of MST (not necessarily as Kruskal's algorithm order) and check if they are critical, pseudo-critical, or neither.

To check if an edge is critical:

1. Remove the current edge from the graph and generate the MST.
2. If the new MST weight is strictly greater than the weight of the previous MST, the edge is critical.
3. Else, it is not the critical edge.

To check if an edge is pseudo-critical:

1. Add the current edge to the graph (cannot use edges from the existing MST because it will make the new tree have cycles and will not be a valid MST).
2. Generate the MST of the new graph.
3. If the weight of the MST equals the weight of the previous MST, the edge is pseudo-critical.
4. Else, it is not a pseudo-critical edge.

Finally, return the two lists: critical edges, and pseudo-critical edges.

Code:

1