Number of Provinces (medium)

Back to course home

0% completed

Vote For New Content

Table of Contents

Contents are not accessible

Problem Statement

There are n cities. Some of them are connected in a network. If City A is directly connected to City B, and City B is directly connected to City C, city A is indirectly connected to City C.

If a group of cities are connected directly or indirectly, they form a province.

Given an n x n matrix isConnected where isConnected[i][j] = 1 if the i<sup>th</sup> city and the j<sup>th</sup> city are directly connected, and isConnected[i][j] = 0 otherwise, determine the total number of provinces.

Examples

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

Expected Output: 2
Justification: Here, city 1 and 2 form a single provenance, and city 3 is one provinces itself.
Example 2:
- Input: isConnected = [1,0,0],[0,1,0],[0,0,1]]

Expected Output: 3
Justification: In this scenario, no cities are connected to each other, so each city forms its own province.
Example 3:
- Input: isConnected = [[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]]

Expected Output: 2
Justification: Cities 1 and 4 form a province, and cities 2 and 3 form another province, resulting in a total of 2 provinces.

Constraints:

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

Try it yourself

Try solving this question here:

Python3

. . . .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible