Topics

# Find the Number of Provinces

Moderate
0/80
Average time to solve is 15m
Contributed by
+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 )
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] ]
``````

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

``````So, there are ‘2’ provinces.
``````
Constraints:
``````1 <= 'n' <= 200