Number of Provinces

Problem Id: 547 Difficulty: Medium


Intuition

Solution


class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        # Edge cases
        if not M:
            return 0

        # Prepare
        n = len(M)
        visited = [False] * n
        ans = 0

        # DFS search for each point
        for i in range(n):
            if visited[i]:
                continue
            self.dfs(visited, M, i)
            ans += 1

        return ans

    def dfs(self, visited, neighbour, i):
        visited[i] = True
        for j, friend in enumerate(neighbour[i]):
            if friend and not visited[j]:
                self.dfs(visited, neighbour, j)