Leetcode 1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

In this Leetcode problem, given a graph, we want to find which edges are in all minimum spanning trees, and which ones are only in some minimum spanning trees.

Problem statement

Solution

This is a cool problem and there are a lot of ways you can think about it, here are the ideas I used to solve it:

1. Sort the edges by weight
2. Build a minimum spanning tree and remember which edges are critical and non critical along the way
3. For each set of edges with same weight we want to know: is the edge useful (or it is creating a cycle with the current graph)?
4. If the edge is useful, once we added all the edges of the same weight, is the edge part of a cycle (and then is non critical)? Then if it is non critical, we want to remove enough of the non critical edges to remove all cycles

So that was fun, here is the full code:

class Solution {
    
    int n;
    Map<Integer, Set<Edge>> mst;
    
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(
            int n, int[][] edges) {
        this.n = n;
        // init sortedEdges 
        TreeMap<Integer, Set<Edge>> sortedEdges = new TreeMap<>();
        int p = edges.length;
        for (int i = 0; i…