Medium

Number of Provinces

LAB

Given an adjacency matrix of connected cities, return the number of connected provinces.

EXAMPLES

Example 1

Input
{
  "isConnected": [
    [
      1,
      1,
      0
    ],
    [
      1,
      1,
      0
    ],
    [
      0,
      0,
      1
    ]
  ]
}

Output
2

FUNCTION SHAPE

isConnected: intMatrix→int

SOLUTION NOTE

This is the same as the connected components question.

Reveal reference solution +

pythonREFERENCE

def findCircleNum(self, isConnected: List[List[int]]) -> int:
    n = len(isConnected)
    visited = set()

    def dfs(city):
        for neighbor in range(n):
            if isConnected[city][neighbor] == 1 and neighbor not in visited:
                visited.add(neighbor)
                dfs(neighbor)

    provinces = 0
    for city in range(n):
        if city not in visited:
            visited.add(city)
            dfs(city)
            provinces += 1

    return provinces

TimeO(n^2)

SpaceO(n)

Open on LeetCode ↗