Advertisement
phanindhar1

Untitled

Apr 15th, 2023
513
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.43 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Solution {
  5.     public static void main(String[] args) {
  6.         Scanner scanner = new Scanner(System.in);
  7.  
  8.         int n = scanner.nextInt();
  9.         int m = scanner.nextInt();
  10.  
  11.         int[][] edges = new int[m][3];
  12.         for (int i = 0; i < m; i++) {
  13.             edges[i][0] = scanner.nextInt();
  14.             edges[i][1] = scanner.nextInt();
  15.             edges[i][2] = scanner.nextInt();
  16.         }
  17.  
  18.         scanner.close();
  19.  
  20.         Solution solution = new Solution();
  21.        
  22.         System.out.println(solution.find(n, m, edges));
  23.     }
  24.     public int find(int n, int m, int[][] edges) {
  25.         Arrays.sort(edges, (a, b) -> Integer.compare(b[2], a[2]));
  26.         int[] parent = new int[n + 1];
  27.         for (int i = 1; i <= n; i++) {
  28.             parent[i] = i;
  29.         }
  30.  
  31.         int totalReward = 0;
  32.         for (int[] edge : edges) {
  33.             int parentA = findParent(edge[0], parent);
  34.             int parentB = findParent(edge[1], parent);
  35.             if (parentA != parentB) {
  36.                 parent[parentB] = parentA;
  37.             } else {
  38.                 totalReward += edge[2];
  39.             }
  40.         }
  41.  
  42.         return totalReward;
  43.     }
  44.  
  45.     private int findParent(int node, int[] parent) {
  46.         if (parent[node] != node) {
  47.             parent[node] = findParent(parent[node], parent);
  48.         }
  49.         return parent[node];
  50.     }
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement