There are n cities. is_connected is an n x n matrix where is_connected[i][j] == 1 means cities i and j are directly linked (the matrix is symmetric and is_connected[i][i] == 1). Links are transitive for grouping purposes: a province is a maximal set of cities that can reach each other through direct links.
Write count_provinces(is_connected) -> int returning the number of provinces.
count_provinces([[1, 0, 1],
[0, 1, 0],
[1, 0, 1]]) # 2 -> {0, 2} and {1}
count_provinces([[1, 0],
[0, 1]]) # 2
Constraints: 1 <= n <= 200, every entry is 0 or 1.
Show hint
each province is a connected component of the graph the matrix describes. Start with n separate groups and merge groups along every link, or explore from each city not yet visited.