Number of Provinces

Try to solve the Number of Provinces problem.

Statement

Let’s say we have nn number of cities, and some of them are connected, while some are not. If a city A is connected directly with city B, and city B is connected directly with city C, then we can say that city A is connected indirectly with city C.

A province is a group of directly or indirectly connected cities with no other cities outside of the group.

An (n×n)(n \times n) matrix, is_city_connected, is given, where is_city_connected[i][j] = 1 indicates that the ithi^{th} and the jthj^{th} cities are directly connected. Otherwise, the value is is_city_connected[i][j] = 0.

Use this information to return the total number of provinces.

Constraints:

  • 1n2001 \leq n \leq 200

  • n==n == is_city_connected.length

  • n==n == is_city_connected[i].length, where 0in0 \leq i \leq n

  • is_city_connected[i][j] is 11 or 00.

  • is_city_connected[i][i] ==1== 1

  • is_city_connected[i][j] ==== is_city_connected[j][i]

Examples

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.