C++ | Easy Solution | BFS and DFS Code
Intuition\nBy seeing the question we can understand that we need to calculate number of components present in the graph. Thus the problem is number of connected
# Intuition\nBy seeing the question we can understand that we need to calculate number of components present in the graph. Thus the problem is number of connected components which can be solved by using DFS/BFS.\n\n# Approach\nFor example we have 3 connected componenets in the graph G i.e. G1,G2,G3. G1 , G2, G3 are not connected to any other components.\n\nLet a,b,c belongs to G1.\nLet d,e,f,g belongs to G2.\nLet h,i belongs to G3.\n\na,b,c are connected to each other directly or indirectly same for d,e,f,g and h,i.\n\nNow if we apply DFS/BFS for any one of the nodes from G1 all the nodes of G1 are marked as visited because all the nodes in G1 are connected directly or indirectly.\n\nLet us check whether a node is visited. If yes continue with next one else apply BFS/DFS on the node which marks visited for the following component.\n\nThe final Answer would be number of DFS/BFS applied on the graph G.\n\n# Complexity\n- Time complexity:\nDFS - O(N+M)\nBFS - O(N+M)\n\nN - Number of Vertices.\nM - Number of Edges.\n\n- Space complexity:\nDFS - O(H)\nBFS - O(W)\n\nH - Maximum Height of the Graph\nW - Maximum Width of the Graph\n\n# DFS Code\n```\nclass Solution {\npublic:\nvoid soln(vector<int>adj[],int node,vector<bool>&vis){\n    vis[node] = 1;\n    for(auto i:adj[node]){\n        if(!vis[i]){\n            soln(adj,i,vis);\n        }\n    }\n}\n    int findCircleNum(vector<vector<int>>& isConnected) {\n        int n = isConnected.size();\n        vector<int>adj[n];\n        for(int i = 0;i<n;i++){\n            for(int j = 0;j<n;j++){\n                if(isConnected[i][j]){\n                adj[i].push_back(j);\n                adj[j].push_back(i);\n                }\n            }\n        }\n        vector<bool>vis(n,0);\n        int ans= 0;\n        for(int i = 0;i<n;i++){\n            if(!vis[i]){\n                soln(adj,i,vis);\n                ans++;\n            }\n        }\n        return ans;\n    }\n};\n```\n# BFS Code\n```\nclass Solution {\npublic:\n    int findCircleNum(vector<vector<int>>& isConnected) {\n        int n = isConnected.size();\n        vector<int>adj[n];\n        for(int i = 0;i<n;i++){\n            for(int j = 0;j<n;j++){\n                if(isConnected[i][j]){\n                adj[i].push_back(j);\n                adj[j].push_back(i);\n                }\n            }\n        }\n        vector<bool>vis(n,0);\n        int ans= 0;\n        for(int i = 0;i<n;i++){\n            if(!vis[i]){\n                ans++;\n                queue<int>q;\n                q.push(i);\n                while(!q.empty()){\n                    int node = q.front();\n                    q.pop();\n                    vis[node] = 1;\n                    for(auto child:adj[node]){\n                        if(!vis[child]){\n                            q.push(child);\n                        }\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Breadth-First Search', 'Graph', 'C++']