Search⌘ K

DIY: Number of Provinces

Understand how to determine the total number of provinces by analyzing a connectivity matrix of cities. Learn to identify groups of directly or indirectly connected cities and implement algorithms to solve this common graph problem in coding interviews.

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 ...