Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Find the Number of Provinces

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
74 upvotes
Asked in companies
AmazonSamsung R&D InstituteIntuit

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

example

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 )
Sample input 1:
3
1 0 0 
0 1 0 
0 0 1 
Sample output 1:
3
Explanation of sample input 1:
Test Case 1:
n = 3, roads = [ [1, 0, 0],
                 [0, 1, 0],
                 [0, 0, 1] ]

sample1

So, there are ‘3’ provinces.
Sample input 2:
4
1 1 0 0 
1 1 0 0 
0 0 1 1 
0 0 1 1 
Sample output 2:
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] ]

sample2

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
Full screen
Console