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, isCityConnected, is given, where isCityConnected[i][j] = 1 indicates that the ithi^{th} and the jthj^{th} cities are directly connected. Otherwise, the value is isCityConnected[i][j] = 0.

Use this information to return the total number of provinces.

Constraints:

  • 1≤n≤2001 \leq n \leq 200

  • n==n == isCityConnected.length

  • n==n == isCityConnected[i].length, where 0≤i≤n0 \leq i \leq n

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

  • isCityConnected[i][i] ==1== 1

  • isCityConnected[i][j] ==== isCityConnected[j][i]

Examples

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