phanindhar1

Untitled

Apr 15th, 2023
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.94 KB | None | 0 0
  1. public int find(int n, int m, int[][] edges) {
  2. Arrays.sort(edges, (a, b) -> Integer.compare(b[2], a[2]));
  3. int[] parent = new int[n + 1];
  4. for (int i = 1; i <= n; i++) {
  5. parent[i] = i;
  6. }
  7.  
  8. int totalReward = 0;
  9. for (int[] edge : edges) {
  10. int parentA = findParent(edge[0], parent);
  11. int parentB = findParent(edge[1], parent);
  12. if (parentA != parentB) {
  13. // Removing this edge would disconnect the graph
  14. parent[parentB] = parentA;
  15. } else {
  16. // Removing this edge would not disconnect the graph
  17. totalReward += edge[2];
  18. }
  19. }
  20.  
  21. return totalReward;
  22. }
  23.  
  24. private int findParent(int node, int[] parent) {
  25. if (parent[node] != node) {
  26. parent[node] = findParent(parent[node], parent);
  27. }
  28. return parent[node];
  29. }
Advertisement
Add Comment
Please, Sign In to add comment