547. Number of Provinces

[fockspaces]

for graph, It's convinient to use DFS and set to record the visted places

1. create find_all_cities, that traverse all cities from source
2. if the city is traversed, add it to visted
3. if find city nearby that never be traversed, traverse it
4. at the outer layer, we can record how many times we access into DFS and return it

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        visited, ans = set(), 0
        def find_all_cities(isConnected, src):
            candidates = isConnected[src]
            for i, candidate in enumerate(candidates):
                if candidate == 1 and i not in visited:
                    visited.add(i)
                    find_all_cities(isConnected, i)
        for i in range(len(isConnected)):
            if i not in visited:
                find_all_cities(isConnected, i)
                ans += 1
        return ans

[fockspaces]

1. the isConnected don't have to be passed to helper function since the scope is outside of DFS
2. improve naming

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def find_all_cities(src):
            candidates = isConnected[src]
            for city, can_go in enumerate(candidates):
                if can_go == 1 and city not in visited:
                    visited.add(city)
                    find_all_cities(city)
        visited, provinces = set(), 0
        for city in range(len(isConnected)):
            if city not in visited:
                find_all_cities(city)
                provinces += 1
        return provinces