C++ | DFS | Number of Islands | Detailed explanation
Goal: We need to connect all the computers (directly or indirectly). We have to return the minimum number of operations that are required to connect the compute
Goal: We need to connect all the computers (directly or indirectly). We have to return the minimum number of operations that are required to connect the computers. An operation consists of removing a cable between two directly connected computers and put it between two disconnected computers.\n\nThis problem is a simple variation of counting the number of islands. \n\nWe know that the minimum number of edges required for a graph with `n` nodes to remain connected is `n - 1`. Similarly, if there are k components in a disconnected graph, then we need at least `k - 1` edges to connect every component.\n\nWith that in our mind, we will start with our **base condition**. If the number of edges in the graph is greater than `n - 1` or not. If not, we will `return -1`.\n\nNext, we will count the number of components (`k`). As I already mentioned, we will need `k - 1` operations to connect the computers (components). And that is our **answer!** \n\nWe can also solve this using Union-Find approach and count the number of components. I solved this problem using DFS and the code is shown below. \n\nPlease leave any of  your doubts/comments in the comments section!\n\n```\nclass Solution {\nprivate:\n    void dfs(vector<vector<int>> &adj, vector<bool> &visited, int src)\n    {\n        visited[src] = true;\n        for(int i : adj[src])\n            if(!visited[i])\n                dfs(adj, visited, i);\n    }\npublic:\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        \n        if(connections.size() < n - 1)\n            return -1;\n        vector<vector<int>> adj(n);\n        for(auto v : connections)\n        {\n            adj[v[0]].push_back(v[1]);\n            adj[v[1]].push_back(v[0]);\n        }\n        vector<bool> visited(n, false);\n        int components = 0;\n        for(int i=0; i<n; i++)\n            if(!visited[i])\n            {\n                dfs(adj, visited, i);\n                components++;\n            }\n        return components - 1;\n    }\n};\n```\n\nIf you liked my explanation, would you be so kind as to upvote my post? It gives me motivation to explain more questions in a detailed manner. Happy coding! :)
['Depth-First Search', 'Recursion', 'C']