from collections import defaultdict, deque
class Solution:
    def findCircleNum(self, isConnected) -> int:
        provinces = 0
        # ToDo: Write Your Code Here.
        # create a set visited to track node that already visited
        # this also used to track matrix adjacent node
        # we then loop through each node and check if it is not visited, we then run a bfs to go through that path
        # that we chase up until we done which also count as 1 province
        visited = [False] * len(isConnected)
        def bfs(city):
            stack = deque()
            stack.append(city)
            while stack:
                city = stack.popleft()
                for i in range(len(isConnected)):
                    if isConnected[city][i] == 1 and not visited[i]:
                        visited[i] = True
                        stack.append(i)

        for city in range(len(isConnected)):
            if not visited[city]:
                visited[city] = True
                bfs(city)
                provinces += 1
        return provinces