Advertisement
phanindhar1

Untitled

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