547: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Initialize the variable visited to an empty set.\n2. Define a function
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Initialize the variable visited to an empty set.\n2. Define a function called dfs that takes the input isConnected, visited, and i.\n3. Check if i is already in the visited set. If it is, return 0.\n4. Add i to the visited set.\n5. Loop through isConnected[i] to check if there are any direct connections between i and j.\n6. If there is a direct connection between i and j, call the dfs function recursively on j.\n7. Return 1 to represent the current province.\n8. Initialize the variable provinces to 0.\n9. Loop through the length of isConnected to check all the cities.\n10. For each city, call the dfs function on it and add the result to provinces.\n11. Return provinces as the total number of provinces.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findCircleNum(self, isConnected: List[List[int]]) -> int:\n        visited = set()  # Initialize visited set\n        \n        # Define depth-first search (dfs) function\n        def dfs(isConnected, visited, i):\n            if i in visited:  # If already visited, return 0\n                return 0\n            visited.add(i)  # Add i to visited set\n            for j in range(len(isConnected[i])):  # Check for direct connections\n                if isConnected[i][j] == 1:\n                    dfs(isConnected, visited, j)  # Recursively call dfs on j\n            return 1  # Return 1 to represent current province\n        \n        provinces = 0  # Initialize provinces count\n        for i in range(len(isConnected)):  # Loop through all cities\n            provinces += dfs(isConnected, visited, i)  # Call dfs on city i and add result to provinces\n        return provinces  # Return total number of provinces\n\n```
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Python', 'Python3']