Number of Connected Components in an Undirected Graph

1package pkg5leetcode.blind75;2 3/*4 * Number of Connected Components in an Undirected Graph | LC 3235 * APPROACH: Union-Find merges edges; count distinct roots.6 * COMPLEXITY: Time O(n alpha(n)), Space O(n)7 */8public class blind75_LC323NumberOfConnectedComponents {9    static int countComponents(int n, int[][] edges) {10        int[] parent = new int[n];11        for (int i = 0; i < n; i++) parent[i] = i;12        for (int[] e : edges) {13            int a = find(parent, e[0]), b = find(parent, e[1]);14            if (a != b) parent[a] = b;15        }16        int comps = 0;17        for (int i = 0; i < n; i++) if (find(parent, i) == i) comps++;18        return comps;19    }20 21    static int find(int[] p, int x) {22        while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; }23        return x;24    }25 26    public static void main(String[] args) {27        check(countComponents(5, new int[][]{{0, 1}, {1, 2}, {3, 4}}) == 2, "case1");28        check(countComponents(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 4}}) == 1, "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}