Advertisement
phanindhar1

Untitled

Apr 15th, 2023
550
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.82 KB | None | 0 0
  1.     public int find(int n, int m, int[][] edges) {
  2.         // Sort edges by decreasing order of reward
  3.         Arrays.sort(edges, (a, b) -> Integer.compare(b[2], a[2]));
  4.  
  5.         // Initialize disjoint-set data structure
  6.         int[] parent = new int[n + 1];
  7.         for (int i = 1; i <= n; i++) {
  8.             parent[i] = i;
  9.         }
  10.  
  11.         // Use Kruskal's algorithm to find minimum spanning tree
  12.         int totalReward = 0;
  13.         for (int[] edge : edges) {
  14.             int parentA = findParent(edge[0], parent);
  15.             int parentB = findParent(edge[1], parent);
  16.             if (parentA != parentB) {
  17.                 // Removing this edge would disconnect the graph
  18.                 parent[parentB] = parentA;
  19.                 totalReward += edge[2];
  20.             }
  21.         }
  22.  
  23.         return totalReward;
  24.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement