Data Structures19 sections · 729 units
Open in Course

Problem - Number of Provinces

Friend circles as components

Given an n×nn \times n matrix isConnected where isConnected[i][j] = 1 means city ii and city jj are directly connected, return the number of provinces.

A province is a group of directly or indirectly connected cities. Example:

isConnected = [[1,1,0],
               [1,1,0],
               [0,0,1]]

Returns 22 (cities 0,1 form one province; city 2 alone).

You're finding connected components on an adjacency matrix. Constraints: nn from 11 to 200200.