Efficient DFS Solution for Provinces 🚀🗺️| Beats 90% in Speed
Intuition\nThe problem involves identifying groups of interconnected cities, which can be visualized as finding connected components in an undirected graph. Ini
# Intuition\nThe problem involves identifying groups of interconnected cities, which can be visualized as finding connected components in an undirected graph. Initially, the thought process involves recognizing that each city and its direct or indirect connections form a distinct group, or province. DFS is an efficient way to traverse these connections and group cities into provinces.\n# Approach\nTo solve the problem, we use Depth-First Search (DFS). Here\'s the step-by-step approach:\n\n1. Initialize a set `visited` to keep track of cities that have already been explored.\n2. Iterate over each city in the matrix. For each unvisited city, initiate a DFS to explore all cities that are connected to it, marking them as visited.\n3. Each DFS initiation from an unvisited city represents the discovery of a new province, so increment the province count accordingly.\n\nThe DFS function will recursively visit each city that is directly connected to the current city, and mark all reachable cities as visited. This ensures that all cities within the same province are identified and marked in a single DFS traversal.\n\n\n\n# Complexity\n- Time complexity: $$O(n^2)$$ because we potentially check every connection between the cities in the `isConnected` matrix. Each city is visited once, and for each visit, we could traverse its connections, leading to a quadratic time complexity.\n\n- Space complexity:\n$$O(n)$$. This is due to the space required for the `visited` set, which stores up to `n` cities, and the recursion stack used by DFS, which, in the worst case, can grow up to the size of `n` if the cities form a single large connected component.\n\n# Code\n```\nclass Solution:\n    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n        def dfs(city):\n            for neighbor, connected in enumerate(isConnected[city]):\n                if connected == 1 and neighbor not in visited:\n                    visited.add(neighbor)\n                    dfs(neighbor)\n\n        n_provinces = 0\n        visited = set()\n        for city in range(len(isConnected)):\n            if city not in visited:\n                visited.add(city)\n                dfs(city)\n                n_provinces += 1\n\n        return n_provinces\n```
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Graph', 'Python3']