Number of Provinces

Statement

Let’s say we have $n$ 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 \times n)$ matrix, isCityConnected, is given, where isCityConnected[i][j] = 1 indicates that the $i^{th}$ and the $j^{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 \leq n \leq 200$

• $n ==$ isCityConnected.length

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

• isCityConnected[i][j] is $1$ or $0$.

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

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

Examples