[백준/자바] #21924

MST(minimum spanning tree) 문제였고, 나는 Kruskal 알고리즘으로 풀었다. 

import java.io.*;
import java.util.*;

class Main {

    static class Node implements Comparable<Node> {
        int start;
        int end;
        int weight;
        public Node(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Main.Node o) {
            return this.weight - o.weight;
        }
    }

    static int N, M, connectedCount;
    static long allWeight, solution;
    static Node[] graph;
    static int[] parent;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        connectedCount = 0;
        allWeight = solution = 0L;

        graph = new Node[M];
        parent = new int[N+1];

        for(int i=1; i<N+1; i++) {
            parent[i] = i;
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            graph[i] = new Node(start, end, weight);
            allWeight += (long) weight;
        }
        Arrays.sort(graph);
        br.close();

        solution();

        if(connectedCount != N-1) {
            System.out.println("-1");
        } else {
            System.out.println((allWeight - solution));
        }
    }

    private static int findParent(int node) {
        if(parent[node] == node) {
            return parent[node];
        }
        parent[node] = findParent(parent[node]);
        return parent[node];
    }

    private static void union(int nodeA, int nodeB) {
        int parentA = findParent(nodeA);
        int parentB = findParent(nodeB);
        if (parentA < parentB) {
            parent[parentB] = parentA;
        } else if (parentA > parentB) {
            parent[parentA] = parentB;
        }
    }

    private static void solution() {
        for(Node node : graph) {
            int startParent = findParent(node.start);
            int endParent = findParent(node.end);
            if(startParent != endParent) {
                union(node.start, node.end);
                solution += (long) node.weight;
                connectedCount++;
            }
        }
    }
}