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; } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter