DIY: Number of Provinces
Solve the interview question "Number of Provinces" in this lesson.
We'll cover the following...
Problem statement
Suppose there are n
cities, where some are connected, while others are not.
If a city c1
is connected to city c2
, and city c2
is connected to city c3
, then c1
is indirectly connected to c3
.
A group of directly or indirectly connected cities, where no other city is part of this group, is called a province.
You are given a matrix, is_connected
with a size of n x n
. An entry is_connected[i][j] = 1
if the ...