Q30 Minimum Spanning Tree | Practice | GeeksforGeeks (kruskal algo)

class Solution{
	static int spanningTree(int V, int E, int edges[][]){
	    //already submitted through prims , now through kruskal
	    
	    int ans =0;
	    
	    Arrays.sort(edges , (a, b) -> a[2] - b[2]); //sort ascending order of weights
	    
	    DSU temp = new DSU(V);  //making DSU
	    
	    //taking sorted edges and processing them 1 by 1
	    for(int i = 0 ; i < edges.length ; i++){
	        int edge[] = edges[i];
	        int a = edge[0] , b = edge[1] , wt = edge[2];
	        
	        //if an edge already has a leader this will fail as that will make a cycle
	        if(temp.union(a , b , temp.parent , temp.rank)){
	            ans += edge[2];
	        }
	    }
	    return ans;
	    
	}
	//DSU template
	public static class DSU{
        int parent[] , rank[];

        DSU(int n ){
            parent = new int[n];
            rank = new int[n];

            for(int i = 0 ;i < n ; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public static int find(int child , int parent[]) {
            //if it is its own parent
            if(parent[child] == child){
                return parent[child];
            }

            int temp  = find(parent[child] , parent);    //optimization 1 (path compression)
            parent[child] = temp;

            return temp;
        }

        //x and y are childrens
        public static boolean union(int x , int y , int parent[] , int rank[]){
            //finding leaders
            int lx = find(x , parent);
            int ly = find(y , parent);
            
            //combining based on ranks
            if(lx != ly){
                if(rank[lx] > rank[ly]){
                    parent[ly] = lx;
                }
                else if(rank[lx] < rank[ly]){
                    parent[lx] = ly;
                }

                else{
                    parent[lx] = ly;
                    rank[ly] ++ ;
                }
                return true;
            }
            return false;
        }
        
    }

}