Minimum Spanning Tree (Kruskal)

/*
 * Problem : Minimum spanning tree.
 * Input   : n and m, then m weighted edges.
 * Output  : The total weight or disconnected.
 * Approach: Kruskal.
 * Time    : O(m log m)
 * Space   : O(n + m)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Find the root of a node. Path halving keeps the paths short.
        static int find(int[] parent, int node) {
            while (parent[node] != node) {
                parent[node] = parent[parent[node]];
                node = parent[node];
            }
            return node;
        }

    // This method solves the task. It receives the input and returns the answer.
    static String solve(String[] lines) {
        String[] header = lines[0].split(" ");
        int n = Integer.parseInt(header[0]);
        int m = Integer.parseInt(header[1]);

        // Step 1: Read the edges as {weight, a, b} and sort them from the cheapest to the most expensive.
        long[][] edges = new long[m][];
        for (int i = 0; i < m; i++) {
            String[] part = lines[i + 1].split(" ");
            edges[i] = new long[] {Long.parseLong(part[2]), Long.parseLong(part[0]), Long.parseLong(part[1])};
        }
        java.util.Arrays.sort(edges, (x, y) -> Long.compare(x[0], y[0]));

        // Step 2: Union-Find keeps the groups of nodes that are already connected.
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        long total = 0;
        int used = 0;
        for (long[] edge : edges) {
            int rootA = find(parent, (int) edge[1]);
            int rootB = find(parent, (int) edge[2]);

            // Step 3: Take an edge only if it joins two different groups. Then it cannot make a cycle.
            if (rootA != rootB) {
                parent[rootA] = rootB;
                total += edge[0];
                used++;
            }
        }

        // Step 4: A spanning tree of n nodes has exactly n - 1 edges. Fewer edges means the graph is not connected.
        return used == n - 1 ? String.valueOf(total) : "disconnected";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}