Number of Provinces

Graph
Medium

Approach

Diagrams

Analysis

Time

O(n^2)

Space

O(n)
from collections import deque


class Solution:
    def findCircleNum(self, graph):
        numProvinces = 0
        visited = set()

        for cityNum, connections in enumerate(graph):
            if cityNum in visited:
                continue

            self.bfs(graph, visited, cityNum, connections)

            numProvinces += 1

        return numProvinces

    def bfs(self, graph, visited, cityNum, connections):
        queue = deque(enumerate(connections))
        visited.add(cityNum)

        while queue:
            otherCityNum, isConnected = queue.popleft()
            if otherCityNum in visited or not isConnected:
                continue

            queue.extend(enumerate(graph[otherCityNum]))
            visited.add(otherCityNum)

Learn

#Breadth-First Search

Videos