| 4 | |
| 5 | class Solution { |
| 6 | static int spanningTree(int V, int E, List<List<int[]>> adj) { |
| 7 | // Code Here. |
| 8 | //(parent, node, weight) |
| 9 | PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<>(){ |
| 10 | public int compare(int pair1[], int pair2[]){ |
| 11 | return pair1[2] - pair2[2]; |
| 12 | } |
| 13 | }); |
| 14 | int sum=0; |
| 15 | ArrayList<int[]> edges = new ArrayList<>(); |
| 16 | boolean visited[] = new boolean[V]; |
| 17 | pq.offer(new int[]{-1,0,0}); |
| 18 | while(!pq.isEmpty()){ |
| 19 | int object[] = pq.poll(); |
| 20 | int parent = object[0]; |
| 21 | int node = object[1]; |
| 22 | int weight = object[2]; |
| 23 | if(visited[node]) continue; |
| 24 | visited[node] = true; |
| 25 | if(parent!=-1){ |
| 26 | edges.add(new int[]{parent, node}); |
| 27 | sum += weight; |
| 28 | } |
| 29 | |
| 30 | for(int neighbourObject[] : adj.get(node)){ |
| 31 | int neighbourNode = neighbourObject[0]; |
| 32 | int neighbourWeight = neighbourObject[1]; |
| 33 | if(!visited[neighbourNode]){ |
| 34 | pq.offer(new int[]{node,neighbourNode,neighbourWeight}); |
| 35 | } |
| 36 | } |
| 37 | } |
| 38 | return sum; |
| 39 | } |
| 40 | } |