---
title: 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
tags: graph
description: share source code.
---

# 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

class Solution {
    
    int root [] = new int [101];
    int rank [] = new int [101];
    int component = 0;
    
    public void init(){
        for(int i = 0; i < 101; i++){
            root [i] = i;
            rank [i] = 1;
        }
         component = 0;
    } 
    
    public boolean isConnected(int u, int v){
        return find(u) == find(v);
    }
    
    public void union(int u, int v){
        int pu = find(u); 
        int pv = find(v);
        if(rank[pu] < rank[pv]){
            root [pu] = pv;
        }else if(rank[pu] > rank[pv]){
            root [pv] = pu;
        }else{
            root [pv] = pu;
            rank [pu]++;
        }
         component++;
    }
    
    public int find(int u){
        while(u != root[u]){
            root[u] = root[root[u]];
            u = root[u];
        }
        return u;
    }
    
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
           int m = edges.length;
           init();
           
            Map<int[], Integer> map = new HashMap<>();
            for(int i =0;i<edges.length;i++){
                map.put(edges[i], i);
            }
        
        
           Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        
           int min_cost = 0;
           int min_component = 0;
           for(int edge [] : edges){
               if(!isConnected(edge[0], edge[1])){
                   union(edge[0], edge[1]);
                   min_cost += edge[2];
                   min_component = component;
               }
           } 
         
          //System.out.println("min_cost: " + min_cost + " component " + component);
        
           List<Integer> critical_edges = new ArrayList<>();
           List<Integer> pseudo_edges = new ArrayList<>();
        
          
           for(int i = 0; i < m; i++){
               init();
               int new_min_cost = 0;
              
                     
               int [] this_edge = edges[i];
               
               for(int j = 0; j < m; j++){
                   if( i == j){
                       continue;
                   }
                   int [] edge = edges[j];
                   
                   if(!isConnected(edge[0], edge[1])){
                       union(edge[0], edge[1]);
                       new_min_cost += edge[2];
                   }
               }
               
               if(new_min_cost == min_cost){
                   // check if it is in MST => must include this edge and doesn't increase min_cost
                   init();
                  // include this edge
                  union(this_edge[0], this_edge[1]);
                  
                  // include this edge weight
                   new_min_cost = this_edge[2];
                   
                    for(int edge [] : edges){
                       if(!isConnected(edge[0], edge[1])){
                           union(edge[0], edge[1]);
                           new_min_cost += edge[2];
                       }
                   }  
                   //System.out.println("include edge " + i +" new_min_cost: " + new_min_cost+ " component " + component);
                   if(new_min_cost == min_cost)
                       pseudo_edges.add(map.get(this_edge));   
                 
                   
               }else if(new_min_cost > min_cost || min_component != component){
                  critical_edges.add(map.get(this_edge));
               }
               
           }
        
           return Arrays.asList(critical_edges, pseudo_edges);
        
    }
}