✅C++ | ✅DFS | ✅Easy & Efficient Approach
Intuition\nWe can use dfs to find total number of disconnected computers.\n\n# Complexity\n### Time complexity:\nO(N+E): dfs + O(N+E): creating adjacency list \
# Intuition\nWe can use dfs to find total number of disconnected computers.\n\n# Complexity\n### Time complexity:\nO(N+E): dfs + O(N+E): creating adjacency list \n~**O(N+E)**\n\n### Space complexity:\nO(N): visited vector + O(N+E): adjacency list + O(N): recursion auxiliary space\n~**O(N+E)**\n\nwhere N: number of nodes, E: number of edges\n\n# Code\n```\nclass Solution \n{\npublic:\n\n    //Mark connected computers as visited in vis vector by using dfs.\n    void dfsConnectedComputers(int node, vector<int> adj[], vector<int> &vis)\n    {\n        vis[node]=1;\n        for(auto &it:adj[node])\n        {\n            if(!vis[it])\n                dfsConnectedComputers(it, adj, vis);\n        }\n    }\n\n    int makeConnected(int n, vector<vector<int>>& connections) \n    {\n        int edges = connections.size();\n        if(edges<n-1) return -1; //Minimum no. of egdes should be (n-1).\n        vector<int> adj[n];\n        for(auto &it:connections) //creating adjacency list\n        {\n            adj[it[0]].push_back(it[1]);\n            adj[it[1]].push_back(it[0]);\n        }\n\n        vector<int> vis(n,0);\n        int disconnected=0;\n        \n        for(int node=0; node<n; node++) //count disconnected computers\n        {\n            if(!vis[node]) \n            {\n                disconnected++;\n                dfsConnectedComputers(node, adj, vis);\n            }\n        }\n    \n        return disconnected-1;\n    }\n};\n```\n# Please upvote if you like this approach :)
['Depth-First Search', 'Graph', 'C++']