Marc Lester Tan

class Solution {
    class DisjointSet {
        
        private Map<Integer, Node> mapping = new HashMap<>();
        
        class Node {
            int rank;
            int data;
            Node parent;
        }
        
        public void makeSet(int n){
            Node node = new Node();
            node.rank = 0;
            node.data = n;
            node.parent = node;
            mapping.put(n, node);
        }
        
        public void union(int x, int y){
            if(mapping.containsKey(x) && mapping.containsKey(y)){
                Node xNode = mapping.get(x);
                Node yNode = mapping.get(y);
                
                Node xSet = findSet(xNode);
                Node ySet = findSet(yNode);
                
                if(xSet == ySet) return;
                
                // union by rank
                if(xSet.rank >= ySet.rank){
                    xSet.rank = xSet.rank == ySet.rank ? xSet.rank + 1 : xSet.rank;
                    ySet.parent = xSet;
                }else{
                    xSet.parent = ySet;
                }
            }            
        }
        
        public int findSet(int data){
            return findSet(mapping.get(data)).data;
        }
        
        public Node findSet(Node node){
            Node parent = node.parent;
            if(node == parent) return node;
            
            // path compression
            node.parent = findSet(node.parent);
            return node.parent;
        }
    }
    
    
    public int minimumCost(int N, int[][] connections) {
        // use kruskal's algorithm
        
        // sort the edges' weights in increasing order
        
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        
        // create the disjoint set
        DisjointSet ds = new DisjointSet();
        for(int i=1 ; i <= N; i++){
            ds.makeSet(i);
        }
        
        int result = 0;
        
        // build the connected components
        for(int[] connection : connections){
            int a = ds.findSet(connection[0]);
            int b = ds.findSet(connection[1]);
        
            // if they are not on the same set, add the weight
            if(a != b){
                result += connection[2];
                
                // then union them
                ds.union(a, b);
            }
        }
        
        // check if there's only 1 big connected component
        int root = ds.findSet(1);
        for(int i=2 ; i <= N; i++){
            if(root != ds.findSet(i)) return -1;
        }
                
        return result;
    }
}