[Java] Count number of connected components - Clean code
\u2714\uFE0F Solution 1a: Naive Union-Find ~ 23ms\njava\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.l
**\u2714\uFE0F Solution 1a: Naive Union-Find ~ 23ms**\n```java\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) return -1; // To connect all nodes need at least n-1 edges\n        int[] parent = new int[n];\n        for (int i = 0; i < n; i++) parent[i] = i;\n        int components = n;\n        for (int[] c : connections) {\n            int p1 = findParent(parent, c[0]);\n            int p2 = findParent(parent, c[1]);\n            if (p1 != p2) {\n                parent[p1] = p2; // Union 2 component\n                components--;\n            }\n        }\n        return components - 1; // Need (components-1) cables to connect components together\n    }\n    private int findParent(int[] parent, int i) {\n        while (i != parent[i]) i = parent[i];\n        return i; // Without Path Compression\n    }\n}\n```\nComplexity:\n- Time: `O(n*m)`, `m` is the length of connections. Can cause **TLE** with this testcase:  https://ideone.com/ZQHtLm\n- Space: `O(n)`\n\n---\n\n**\u2714\uFE0F Solution 1b: Union-Find with Path Compression ~ 3ms**\n```java\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) return -1; // To connect all nodes need at least n-1 edges\n        int[] parent = new int[n];\n        for (int i = 0; i < n; i++) parent[i] = i;\n        int components = n;\n        for (int[] c : connections) {\n            int p1 = findParent(parent, c[0]);\n            int p2 = findParent(parent, c[1]);\n            if (p1 != p2) {\n                parent[p1] = p2; // Union 2 component\n                components--;\n            }\n        }\n        return components - 1; // Need (components-1) cables to connect components together\n    }\n    private int findParent(int[] parent, int i) {\n        if (i == parent[i]) return i;\n        return parent[i] = findParent(parent, parent[i]); // Path compression\n    }\n}\n```\nComplexity:\n- Time: `O(n+mlogn)`, `m` is the length of connections\n- Space: `O(n)`\n\n---\n\n**\u2714\uFE0F Solution 1c: Union-Find with Path Compression and Union by Size ~ 3ms**\n```java\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) return -1; // To connect all nodes need at least n-1 edges\n        int[] parent = new int[n];\n        int[] size = new int[n];\n        for (int i = 0; i < n; i++) {\n            parent[i] = i;\n            size[i] = 1;\n        }\n        int components = n;\n        for (int[] c : connections) {\n            int p1 = findParent(parent, c[0]);\n            int p2 = findParent(parent, c[1]);\n            if (p1 != p2) {\n                if (size[p1] < size[p2]) { // Merge small size to large size\n                    size[p2] += size[p1];\n                    parent[p1] = p2;\n                } else {\n                    size[p1] += size[p2];\n                    parent[p2] = p1;\n                }\n                components--;\n            }\n        }\n        return components - 1; // Need (components-1) cables to connect components together\n    }\n    private int findParent(int[] parent, int i) {\n        if (i == parent[i]) return i;\n        return parent[i] = findParent(parent, parent[i]); // Path compression\n    }\n}\n```\nComplexity:\n- Time: `O(n + m*\u03B1(n))` \u2248 `O(n + m)`, `m` is the length of connections (union operations). \n   Explanation: Using both **path compression** and **union by size** ensures that the **amortized time** per operation is only `\u03B1(n)`, which is optimal, where `\u03B1(n)` is the inverse Ackermann function. This function has a value `\u03B1(n) < 5` for any value of n that can be written in this physical universe, so the disjoint-set operations take place in essentially constant time.\nReference: https://en.wikipedia.org/wiki/Disjoint-set_data_structure or https://www.slideshare.net/WeiLi73/time-complexity-of-union-find-55858534 for more information.\n- Space: `O(n)`\n\n---\n\n**\u2714\uFE0F Solution 2: DFS ~ 11ms**\n```java\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) return -1; // To connect all nodes need at least n-1 edges\n        List<Integer>[] graph = new List[n];\n        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();\n        for (int[] c : connections) {\n            graph[c[0]].add(c[1]);\n            graph[c[1]].add(c[0]);\n        }\n        int components = 0;\n        boolean[] visited = new boolean[n];\n        for (int v = 0; v < n; v++) components += dfs(v, graph, visited);\n        return components - 1; // Need (components-1) cables to connect components together\n    }\n    int dfs(int u, List<Integer>[] graph, boolean[] visited) {\n        if (visited[u]) return 0;\n        visited[u] = true;\n        for (int v : graph[u]) dfs(v, graph, visited);\n        return 1;\n    }\n}\n```\nComplexity:\n- Time: `O(n+m)`, `m` is the length of connections\n- Space: `O(n)`\n\n---\n\n**\u2714\uFE0F Solution 3: BFS ~ 12ms**\n```java\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) return -1; // To connect all nodes need at least n-1 edges\n        List<Integer>[] graph = new List[n];\n        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();\n        for (int[] c : connections) {\n            graph[c[0]].add(c[1]);\n            graph[c[1]].add(c[0]);\n        }\n        int components = 0;\n        boolean[] visited = new boolean[n];\n        for (int v = 0; v < n; v++) components += bfs(v, graph, visited);\n        return components - 1; // Need (components-1) cables to connect components together\n    }\n    int bfs(int src, List<Integer>[] graph, boolean[] visited) {\n        if (visited[src]) return 0;\n        visited[src] = true;\n        Queue<Integer> q = new LinkedList<>();\n        q.offer(src);\n        while (!q.isEmpty()) {\n            int u = q.poll();\n            for (int v : graph[u]) {\n                if (!visited[v]) {\n                    visited[v] = true;\n                    q.offer(v);\n                }\n            }\n        }\n        return 1;\n    }\n}\n```\nComplexity:\n- Time: `O(n+m)`, `m` is the length of connections\n- Space: `O(n)`
[]