Skip to content
Onsite
11 / 25

Number of Provinces

MediumP2Coding

There are n cities. isConnected is an n x n matrix where isConnected[i][j] = 1 means city i and city j are directly connected, and 0 means they are not. The matrix is symmetric and isConnected[i][i] = 1.

A province is a group of cities that are connected directly or through other cities, with no connection to cities outside the group. Return the number of provinces.

Example 1

Input
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output
2

Example 2

Input
isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output
3

Constraints

  • 1 <= n <= 200
  • isConnected[i][j] is 0 or 1
  • isConnected[i][i] == 1 and isConnected[i][j] == isConnected[j][i]

Hints

Run checks the 3 visible tests, Submit all 9.