Easy Java Solution Using BFS and disjoint_set || Easy to understand
\n# Complexity\n- Time complexity: O(N+E)\n\n- Space complexity: O(N+E)\n\n# Disjoint_set Code\n1. Crate a disjoint set and initilize it with the connections.\n
\n# Complexity\n- Time complexity: **O(N+E)**\n\n- Space complexity: **O(N+E)**\n\n# Disjoint_set Code\n1. **Crate a disjoint set and initilize it with the connections.**\n2. **Initilize a counter with n-1 connections**\n3. **Now for each new connection check if it belongs to same set , if not decrease the number of connections**\n```\nclass Solution {\n\n    class disjoint_set{\n        List<Integer> rank = new ArrayList<>();\n        List<Integer> parent = new ArrayList<>();\n    \n        disjoint_set(int n){\n            for(int i = 0;i <= n;i++){\n                rank.add(0);\n                parent.add(i);\n            }\n        }\n    \n        public int findUparent(int node){\n            if(node == parent.get(node)){\n                return node;\n            }\n            int res = findUparent(parent.get(node));\n    \n            parent.set(node, res);\n    \n            return parent.get(node);\n        }\n    \n        public boolean union_by_rank(int u, int v){\n            int upu = findUparent(u);\n            int upv = findUparent(v);\n    \n            if(upu == upv){\n                return false;\n            }\n    \n            if(rank.get(upv) > rank.get(upu)){\n                parent.set(upu, upv);\n            }\n            else if(rank.get(upv) < rank.get(upu)){\n                parent.set(upv,upu);\n            }\n            else{\n                parent.set(upv, upu);\n                rank.set(upv, rank.get(upv)+1);\n            }\n\n            return true;\n        }\n    }\n\n    public int makeConnected(int n, int[][] connections) {\n        disjoint_set uf = new disjoint_set(n);\n\n        if (connections.length < n - 1) {\n            return -1;\n        }\n\n        int newConn = n - 1;\n        for (var conn : connections) {\n            if (uf.union_by_rank(conn[0], conn[1])) {\n                newConn--;\n            }\n        }\n\n        return newConn;\n    }\n}\n```\n# BFS Code\n**perform a basic bfs and then return the number of disconnected components -1.**\n```\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if(n-1 > connections.length){\n            return -1;\n        }\n\n        boolean[] visited = new boolean[n];\n\n        int ct = 0;\n\n        HashMap<Integer,List<Integer>> graph = new HashMap<>();\n\n        for(int i = 0;i < connections.length;i++){\n            int u = connections[i][0];\n            int v = connections[i][1];\n\n            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);\n            graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);\n        }\n\n        for(int i = 0;i < n;i++){\n            if(!visited[i]){\n                ct++;\n                bfs(graph,visited,i);\n            }\n        }\n\n        return ct-1;\n    }\n\n    private void bfs(HashMap<Integer,List<Integer>> graph,boolean[] visited, int i){\n        visited[i] = true;\n        Queue<Integer> q = new LinkedList<>();\n        q.offer(i);\n\n        while(!q.isEmpty()){\n            int x = q.poll();\n\n            if(!graph.containsKey(x)){\n                continue;\n            }\n\n            for(int it : graph.get(x)){\n                if(!visited[it]){\n                    visited[it] = true;\n                    q.offer(it);\n                }\n            }\n        }\n    }\n}\n```
['Breadth-First Search', 'Union Find', 'Graph', 'Java']