Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.Scanner;
- public class Solution {
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- int m = scanner.nextInt();
- int[][] edges = new int[m][3];
- for (int i = 0; i < m; i++) {
- edges[i][0] = scanner.nextInt();
- edges[i][1] = scanner.nextInt();
- edges[i][2] = scanner.nextInt();
- }
- scanner.close();
- Solution solution = new Solution();
- System.out.println(solution.find(n, m, edges));
- }
- public int find(int n, int m, int[][] edges) {
- Arrays.sort(edges, (a, b) -> Integer.compare(b[2], a[2]));
- int[] parent = new int[n + 1];
- for (int i = 1; i <= n; i++) {
- parent[i] = i;
- }
- int totalReward = 0;
- for (int[] edge : edges) {
- int parentA = findParent(edge[0], parent);
- int parentB = findParent(edge[1], parent);
- if (parentA != parentB) {
- parent[parentB] = parentA;
- } else {
- totalReward += edge[2];
- }
- }
- return totalReward;
- }
- private int findParent(int node, int[] parent) {
- if (parent[node] != node) {
- parent[node] = findParent(parent[node], parent);
- }
- return parent[node];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement