Medium

Quiz

#547 Number of Provinces

APPROACH

There are n cities. A province is a maximal cluster of cities that are all mutually reachable through direct or indirect connections. You are given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 means cities i and j are directly linked, and 0 means they are not. Return the total number of distinct provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

1 of 4

1:00

What is the optimal approach for this problem?