Advertisement
phanindhar1

Untitled

Apr 15th, 2023
26
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 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. int numComponents = n;
  14. for (int[] edge : edges) {
  15. int parentA = findParent(edge[0], parent);
  16. int parentB = findParent(edge[1], parent);
  17. if (parentA != parentB) {
  18. // Removing this edge would connect two previously disjoint components
  19. parent[parentB] = parentA;
  20. totalReward += edge[2];
  21. numComponents--;
  22. if (numComponents <= 1) {
  23. // All nodes are now in one connected component
  24. break;
  25. }
  26. }
  27. }
  28.  
  29. return totalReward;
  30. }
  31.  
  32. private int findParent(int node, int[] parent) {
  33. if (parent[node] != node) {
  34. parent[node] = findParent(parent[node], parent);
  35. }
  36. return parent[node];
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement