Find the Number of Provinces

Moderate

0/80

Average time to solve is 15m

Contributed by

40 upvotes

+3 more companies

Problem statement

You are given ‘n’ cities, some of which are connected by bidirectional roads. You are also given an ‘n x n’ matrix i.e. ‘roads’, where if city ‘i’ and ‘j’ are connected by a road then ‘roads[i][j]'= 1, otherwise ‘roads[i][j]' = 0.

A province is a group of cities that are either directly or indirectly connected to each other through roads.

The goal is to count and return the total number of such provinces in the given matrix.

Example:

n = 4, roads = [ [1, 1, 1, 0],
                 [1, 1, 1, 0],
                 [1, 1, 1, 0],
                 [0, 0, 0, 1] ]

So, there are ‘2’ provinces.

Note:

1. A city is connected to itself. So, for every city ‘i’, ‘roads[i][i] = 1’.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an integer ‘n’ denoting the number of cities.

Next ‘n’ lines contains ‘n’ space-separated integers denoting a row of ‘roads’.

Output format:

The output contains the number of provinces.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Sample input 1:

Sample output 1:

Explanation of sample input 1:

Test Case 1:
n = 3, roads = [ [1, 0, 0],
                 [0, 1, 0],
                 [0, 0, 1] ]

So, there are ‘3’ provinces.

Sample input 2:

Sample output 2:

Explanation of sample input 2:

n = 4, roads = [ [1, 1, 0, 0],
                 [1, 1, 0, 0],
                 [0, 0, 1, 1],
                 [0, 0, 1, 1] ]

So, there are ‘2’ provinces.

Constraints:

1 <= 'n' <= 200
roads[i][j] is 1 or 0.
roads[i][j] == roads[j][i]

Time limit: 1 sec

Console