[LeetCode] Number of Provinces

 

 

Problem

 

 

---

 

Solution

 

DFS problem

 

Each row = One city

Don't need to look at one more than once -- keep track of them in 'seen' dictionary.

 

Time Complexity

O(n) (n = num of cities)

 

 

Space Complexity

O(N)

 

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        if not isConnected:
            return 0
        
        rows = len(isConnected)
        seen = set()
        count = 0
        
        def dfs(r):
            for index, val in enumerate(isConnected[r]):
                if val == 1 and index not in seen:
                    seen.add(index)
                    dfs(index)
        
        
        for r in range(rows):
            if r not in seen:
                dfs(r)
                count +=1
                
        return count