We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
publicstaticintprims(intn,List<List<Integer>>edges,intstart){//USING PROVIDED DATA APPROACHComparator<List<Integer>>comp=(l1,l2)->{returnl1.get(2)-l2.get(2);};Collections.sort(edges,comp);HashSet<Integer>set=newHashSet<>();set.add(start);intsumMin=0;while(set.size()<n){Iterator<List<Integer>>iter=edges.iterator();while(iter.hasNext()){List<Integer>list=iter.next();intleft=list.get(0);intright=list.get(1);intdistance=list.get(2);//Using LinkedList might speed this up//Actual no need to remove already parsed list// to fit set limitif(set.contains(left)&&set.contains(right)){iter.remove();continue;}if((set.contains(left)&&!set.contains(right))||(!set.contains(left)&&set.contains(right))){sumMin+=distance;set.add(left);set.add(right);break;}}}returnsumMin;/* CREATING SUMMARY ARRAY APPROACH int res = 0; int[][] grid = new int[n + 1][n + 1]; for (List<Integer> list : edges) { int i = list.get(0); int j = list.get(1); int dis = list.get(2); grid[i][j] = dis; grid[j][i] = dis; } HashSet<Integer> set = new HashSet<>(); set.add(start); while (set.size() < n) { TreeMap<Integer, Integer> map = new TreeMap<>(); for (Integer i : set) { for (int j = 1; j < n + 1; j ++) { int curDis = grid[i][j]; if (!set.contains(j) && curDis != 0) { map.put(curDis, j); } } } res += map.firstKey(); set.add(map.firstEntry().getValue()); } return res; */}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Prim's (MST) : Special Subtree
You are viewing a single comment's thread. Return to all comments →
Java8