Count Connected Components (Union-Find)

/*
 * Problem : Count groups.
 * Input   : n and m, then m edge lines.
 * Output  : The number of groups.
 * Approach: Union-Find.
 * Time    : O(m * alpha(n))
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: Each node has a parent. A root is its own parent. Nodes with the same root are in the same group.
        static class UnionFind {
            private final int[] parent;
            private int groups;

            UnionFind(int size) {
                parent = new int[size];
                groups = size;
                for (int i = 0; i < size; i++) {
                    parent[i] = i;
                }
            }

            // Step 2: Find the root. Path halving makes later searches faster.
            int find(int node) {
                while (parent[node] != node) {
                    parent[node] = parent[parent[node]];
                    node = parent[node];
                }
                return node;
            }

            // Step 3: Join two groups. If their roots are different, the number of groups goes down by one.
            void union(int first, int second) {
                int rootFirst = find(first);
                int rootSecond = find(second);
                if (rootFirst != rootSecond) {
                    parent[rootFirst] = rootSecond;
                    groups--;
                }
            }

            int getGroups() {
                return groups;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static int solve(String[] lines) {
        // Step 4: Read n from the first line. Then join the two nodes of every edge line.
        String[] header = lines[0].split(" ");
        UnionFind sets = new UnionFind(Integer.parseInt(header[0]));
        for (int i = 1; i < lines.length; i++) {
            String[] edge = lines[i].split(" ");
            sets.union(Integer.parseInt(edge[0]), Integer.parseInt(edge[1]));
        }
        return sets.getGroups();
    }

    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));
    }
}