🔥Easy Solutions in Java 📝, Python 🐍, and C++ 🖥️🧐Look at once 💻
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to connect all the computers in a network using a minimum number of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to connect all the computers in a network using a minimum number of cables. We can consider each connected component in the network as a separate graph, and we need to connect all the separate graphs into a single graph. We can use the Union-Find algorithm to keep track of the connected components and connect them as required.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. If the number of connections is less than n-1, it is not possible to connect all the computers, so return -1.\n2. Initialize the parent array for the Union-Find algorithm, where parent[i] is the parent of computer i.\n3. Union the connected computers by iterating over the connections array and finding their parent using the find operation in the Union-Find algorithm.\n4. Count the number of disjoint sets (connected components) by iterating over the parent array and counting the number of nodes where parent[i] is equal to i.\n5. The number of cables needed to connect all the computers is equal to the number of disjoint sets minus 1.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\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- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n), as we need to store the parent array for the Union-Find algorithm.\n\n\n\n![image.png](https://assets.leetcode.com/users/images/b427e686-2e5d-469a-8e7a-db5140022a6b_1677715904.0948765.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n```\n# Code\n``` Java []\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        // if there are not enough cables to connect all computers, return -1\n        if (connections.length < n - 1) {\n            return -1;\n        }\n        \n        // initialize parent array for Union-Find algorithm\n        int[] parent = new int[n];\n        for (int i = 0; i < n; i++) {\n            parent[i] = i;\n        }\n        \n        // union connected computers\n        for (int[] connection : connections) {\n            int parent1 = findParent(parent, connection[0]);\n            int parent2 = findParent(parent, connection[1]);\n            if (parent1 != parent2) {\n                parent[parent1] = parent2;\n            }\n        }\n        \n        // count the number of disjoint sets (connected components)\n        int numSets = 0;\n        for (int i = 0; i < n; i++) {\n            if (parent[i] == i) {\n                numSets++;\n            }\n        }\n        \n        // the number of cables needed is equal to the number of disjoint sets minus 1\n        return numSets - 1;\n    }\n    \n    // find the parent of the given node in the Union-Find algorithm\n    private int findParent(int[] parent, int node) {\n        if (parent[node] != node) {\n            parent[node] = findParent(parent, parent[node]);\n        }\n        return parent[node];\n    }\n}\n\n```\n``` C++ []\nclass Solution {\npublic:\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        // if there are not enough cables to connect all computers, return -1\n        if (connections.size() < n - 1) {\n            return -1;\n        }\n        \n        // initialize parent array for Union-Find algorithm\n        vector<int> parent(n);\n        for (int i = 0; i < n; i++) {\n            parent[i] = i;\n        }\n        \n        // union connected computers\n        for (auto connection : connections) {\n            int parent1 = findParent(parent, connection[0]);\n            int parent2 = findParent(parent, connection[1]);\n            if (parent1 != parent2) {\n                parent[parent1] = parent2;\n            }\n        }\n        \n        // count the number of disjoint sets (connected components)\n        int numSets = 0;\n        for (int i = 0; i < n; i++) {\n            if (parent[i] == i) {\n                numSets++;\n            }\n        }\n        \n        // the number of cables needed is equal to the number of disjoint sets minus 1\n        return numSets - 1;\n    }\n    \n    // find the parent of the given node in the Union-Find algorithm\n    int findParent(vector<int>& parent, int node) {\n        if (parent[node] != node) {\n            parent[node] = findParent(parent, parent[node]);\n        }\n        return parent[node];\n    }\n};\n\n```\n``` Python []\nclass Solution(object):\n    def makeConnected(self, n, connections):\n        # if there are not enough cables to connect all computers, return -1\n        if len(connections) < n - 1:\n            return -1\n        \n        # initialize parent array for Union-Find algorithm\n        parent = [i for i in range(n)]\n        \n        # union connected computers\n        for connection in connections:\n            parent1 = self.findParent(parent, connection[0])\n            parent2 = self.findParent(parent, connection[1])\n            if parent1 != parent2:\n                parent[parent1] = parent2\n        \n        # count the number of disjoint sets (connected components)\n        numSets = 0\n        for i in range(n):\n            if parent[i] == i:\n                numSets += 1\n        \n        # the number of cables needed is equal to the number of disjoint sets minus 1\n        return numSets - 1\n    \n    # find the parent of the given node in the Union-Find algorithm\n    def findParent(self, parent, node):\n        if parent[node] != node:\n            parent[node] = self.findParent(parent, parent[node])\n        return parent[node]\n\n```\n\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```
['Depth-First Search', 'Union Find', 'Python', 'C++', 'Java']