C++ | BFS and DFS | Easy to Understand
Intuition\nIf you try to solve a few examples on notebook, you would realise that if we find the number of components that are connected together, the number of
# Intuition\nIf you try to solve a few examples on notebook, you would realise that if we find the number of components that are connected together, the number of cables needed to connect them would be number of connected components-1. \n\n#### Example\n```\n      o --- 1      4 --- 5       \n      |     |                      \n      2 --- 3      6   \n\n```\nIn this diagram, we have three different connected components:\n```\n[0,1,2,3], [4,5], [6]\n```\nWe can see that there are two cables needed to connect all of the components together (which is not possible here).\n# Approach\n- First for both BFS and DFS we need an adjacency matrix to store all the nodes connected to a node. \n- We also need a visited array that will mark the nodes visited.\n- We will loop over all the nodes and check if the node is visited or not. \nIf not, then it is a part of connected component that is unvisited. We will increase the count and call bfs/dfs to mark the nodes that are part of this component as visited\n- In the BFS approach we will use a queue to traverse the nodes connected and mark them visited. While in DFS, we will recursively mark the nodes which are connected to the current node. \n\n\n# Code\n## BFS\n```\nclass Solution {\npublic:\n    // to mark the nodes reachable from curr as visited\n    void bfs(vector<vector<int>>& adj,int curr, vector<bool>& vis ){\n        queue<int>q;\n        q.push(curr);\n        vis[curr]=true;\n        while(!q.empty()){\n            curr=q.front();\n            q.pop();\n            for(auto& node:adj[curr]){\n                if(!vis[node]){ \n                    vis[node]=true;\n                    q.push(node);\n                }\n            }\n        }\n    }\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        if(connections.size()<n-1) return -1; // if the number of connections is less than n-1 that means that we cannot connect all nodes reachable\n\n        vector<bool>vis(n,false);\n        vector<vector<int>>adj(n); // adjacency matrix\n        for(auto& c:connections){\n            adj[c[0]].push_back(c[1]);\n            adj[c[1]].push_back(c[0]);\n        }\n        int conn=-1;\n        for(int i=0;i<n;++i){\n            if(!vis[i]){ // if not visited, a connected component is present that is unvisited\n                ++conn; \n                bfs(adj,i,vis);\n            }\n        }\n        return conn;\n    }\n};\n```\n## DFS\n```\nclass Solution {\npublic:\n    void dfs(vector<vector<int>>& adj,int curr, vector<bool>& vis ){\n        vis[curr]=true;\n        for(auto& node:adj[curr]){\n            if(!vis[node]){\n                dfs(adj,node,vis);\n            }\n        }\n    }\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        if(connections.size()<n-1) return -1;\n\n        vector<bool>vis(n,false);\n        vector<vector<int>>adj(n); // adjacency matrix\n        for(auto& c:connections){\n            adj[c[0]].push_back(c[1]);\n            adj[c[1]].push_back(c[0]);\n        }\n        int conn=-1;\n        for(int i=0;i<n;++i){\n            if(!vis[i]){ // if not visited, a connected component is present that is unvisited\n                ++conn;\n                dfs(adj,i,vis);\n            }\n        }\n        return conn;\n    }\n};\n```
['C++']