Clean Code with easy explanation DFS/BFS code || C++ || DFS || BFS
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem is asking for a province which is a group of directly or indirectly connec
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem is asking for a province which is a group of directly or indirectly connected cities, which is basically a connected component in a graph problem, that is we can achieve this easily with the help of Depth First Search and Breadth First Search\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nApproach is basically we would call DFS or BFS, 1 DFS/BFS call would visit 1 whole province(connected component) so by maintaining a visited array, the no. of calls to unvisited cities for dfs/bfs would be the no. of provinces\n\n# Complexity\n- Time complexity: O(n), Every city will be visited once only\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# DFS approach:\n```\nclass Solution {\npublic:\n    void dfs(vector<vector<int>>& isConnected, int i, vector<int>& visited){\n        int n = isConnected.size();\n        if(visited[i]==1) return; //checking if already visited then return\n\n        visited[i] = 1; //marking visited\n        for(int j=0;j<n;j++){\n            // calling to all cities connected to it through recursion\n            if(isConnected[i][j]==1) dfs(isConnected,j,visited);\n        }\n    }\n\n    int findCircleNum(vector<vector<int>>& isConnected) {\n        //very simple dfs problem, classical \n        int n = isConnected.size();\n        vector<int> visited(n,0);\n        int ans=0;\n        for(int i=0;i<n;i++){\n            if(visited[i]==0){ // calling only if not visited\n                ans++;\n                dfs(isConnected,i,visited);\n            }\n        }\n        return ans;\n    }\n};\n\n```\n# **BFS approach solution (done with queue):**\n```\nclass Solution {\npublic:\n    void bfs(vector<vector<int>>& isConnected, int i, vector<int>& visited){\n        int n = isConnected.size();\n\n        queue<int> q;\n        q.push(i);\n        while(!q.empty()){\n            int temp = q.front();\n            q.pop();\n            visited[temp]=1;\n            for(int j=0;j<n;j++){\n                if(isConnected[temp][j]==1 && visited[j]==0) q.push(j);\n            }\n        }\n    }\n\n    int findCircleNum(vector<vector<int>>& isConnected) {\n        int n = isConnected.size();\n        vector<int> visited(n,0);\n        int ans=0;\n        \n        for(int i=0;i<n;i++){\n            if(visited[i]==0){\n                ans++;\n                bfs(isConnected,i,visited);\n            }\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Breadth-First Search', 'Graph', 'C++']