Number of Provinces

Given n cities, some are connected directly while others indirectly. A province is a group of directly or indirectly connected cities, and no cities outside the group. You are provided an n x n matrix isConnected where isConnected[i][j] = 1 if cities i and j are directly connected, and isConnected[i][j] = 0 otherwise. Determine the total number of provinces.

Constraints

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] is 1 or 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]
View editorial solution
Saving… · 3 lines
class Solution:
def numberOfProvinces(self, isConnected: List[List[int]]) -> int:

Console

Click Run to execute sample tests.