Striver Sheet||🔥Easy C++ Solution Using DFS || Beats 96.47%
\n\n# Intuition\nA province is a group of directly or indirectly connected cities and no other cities outside of the group. Considering the above example, we ca
![image.png](https://assets.leetcode.com/users/images/afff9c02-5690-4ef5-bf4d-712f19e5eccd_1709638920.1409924.png)\n\n# Intuition\nA province is a group of directly or indirectly connected cities and no other cities outside of the group. Considering the above example, we can go from 1 to 2 as well as to 3, from every other node in a province we can go to each other. As we cannot go from 2 to 4 so it is not a province. We know about both the traversals, Breadth First Search (BFS) and Depth First Search (DFS). We can use any of the traversals to solve this problem because a traversal algorithm visits all the nodes in a graph. In any traversal technique, we have one starting node and it traverses all the nodes in the graph. Suppose there is an \u2018N\u2019 number of provinces so we need to call the traversal algorithm \u2018N\u2018 times, i.e., there will be \u2018N\u2019 starting nodes. So, we just need to figure out the number of starting nodes.\n\n# Approach\n1. We initialize a vector `visited` to keep track of visited cities. Initially, all cities are marked as not visited.\n2. We iterate through each city, and if a city is not visited, we perform DFS to traverse all directly and indirectly connected cities.\n3. During DFS, we mark each visited city as visited in the `visited` vector.\n4. We increment the province count every time we start DFS from an unvisited city.\n5. Finally, we return the total number of provinces.\nThe number of provinces signify no. of component in graph\n# Complexity\n- Time complexity: O(N) + O(V+2E), Where O(N) is for outer loop and inner loop runs in total a single DFS over entire graph, and we know DFS takes a time of O(V+2E). \n- Space complexity: O(n), where n is the number of cities. We use the `visited` vector to keep track of visited cities.\n# Code\n```\nclass Solution {\npublic:\n    void dfs(int i, vector<int>&visited, std::vector<std::vector<int>>& roads) {\n    visited[i] = 1;\n    for (int j=0;j<roads[i].size();j++) {\n        if(roads[i][j]==0)continue;\n        if (visited[j]==0) {\n            dfs(j, visited, roads);\n        }\n    }\n}\n    int findCircleNum(vector<vector<int>>& roads) {\n        int n=roads.size();\n        vector<int>visited(n,0); \n    int ans = 0;\n    for (int i = 0; i < n; i++) {\n        if (visited[i]==0) {\n            ans++;\n            dfs(i, visited, roads);\n        }\n    }\n    return ans;\n    }\n};\n```
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Graph', 'C++']