✅ Java | Easy to understand solution 🚀 | Explained
Intuition\nSince the problem is asking us to connect all the computers together using minimum cables. This means that there are computers which are not connecte
# Intuition\nSince the problem is asking us to connect all the computers together using minimum cables. This means that there are computers which are not connected to each other or there are different connected components(single node or multiple nodes connected)\n\nFirst thing that should come to our minds to identify different connected components in graphs is Union Find algorithm.\n\nSome special cases:\n1) If the connections(edges) are less that n-1, then we will not be able to connect all computer(nodes) return -1.\nexample: if there are 4 nodes we need minimum n-1 i.e 4-1= 3 edges(connections) to connect them.\n\n# Approach\n1) Apply union find.\n2) Number of cables would iterating over the parent array finding the number of disjoint sets or different connected components -1\n\n# Complexity\n- Time complexity:\nO(n + Elog(V)), where n is the number of computers, E is the number of connections, and V is the number of disjoint sets. The Union-Find algorithm has a time complexity of O(Elog(V)), and we need to iterate over the connections array once, which takes O(E) time. Counting the number of disjoint sets takes O(n) time.\n\n\n- Space complexity:\nO(n) since we are using it to store parent array.\n# Code\n```\nclass Solution {\n    \n    class UnionFind{\n        int [] parent;\n\n        public UnionFind(int n){\n            parent = new int[n];\n            for(int i=0; i<n; i++){\n                parent[i]=i;\n            }\n        }\n\n        private int find(int x){\n            if(parent[x]!=x){\n                parent[x] = find(parent[x]);\n            }\n            return parent[x];\n        }\n    }\n\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) {\n            return -1;\n        }\n\n        int uniqueSets = 0;\n        UnionFind uf = new UnionFind(n);\n        for(int [] eachConnection : connections){\n            int findU = uf.find(eachConnection[0]);\n            int findV = uf.find(eachConnection[1]);\n            if(findU!=findV){\n                uf.parent[findV] = findU;\n            }\n        }\n\n        /* finding unique connected components(disjoint sets) */\n        for(int i=0; i<uf.parent.length; i++){\n            if(uf.parent[i]==i){\n                uniqueSets++;\n            }\n        }\n\n        return uniqueSets-1;\n    }\n}\n\n```\n
['Union Find', 'Java']