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, is_city_connected, is given, where is_city_connected[i][j] = 1 indicates that the $i^{th}$ and the $j^{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:

• $1 \leq n \leq 200$

• $n ==$ is_city_connected.length

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

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

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

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

Examples