Number of Provinces
Try to solve the Number of Provinces problem.
We'll cover the following
Statement
Let’s say we have 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 matrix, isCityConnected
, is given, where isCityConnected[i][j] = 1
indicates that the and the cities are directly connected. Otherwise, the value is isCityConnected[i][j] = 0
.
Use this information to return the total number of provinces.
Constraints:
-
-
isCityConnected.length
-
isCityConnected[i].length
, where -
isCityConnected[i][j]
is or . -
isCityConnected[i][i]
-
isCityConnected[i][j]
isCityConnected[j][i]
Examples
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.