Find the Number of Provinces

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
87 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 )
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:
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
Hint

Think of using Union-find data structure.

Approaches (3)
Use Disjoint-set data structure

Disjoint-set (or Union-find) is a data structure that stores a collection of disjoint (non-overlapping) sets. This data structure consists of three basic operations:

  • makeSet(‘V’): Create a new set containing the element 'V'.
  • unionSet(‘A’, ‘B’): Merge the two specified sets, the set containing element ‘A’ and the set containing element ‘B’.
  • findSet('V'): Return the representative (also called leader) of the set containing the element 'V'.

 

The idea is to use a Disjoint-set 'DS’, which initially stores ‘n’ sets, each containing a single city. After that, for each pair of cities ‘i’ and ‘j’ that are connected by a road (i.e., ‘ROADS[i][j] = 1’), we merge the two sets containing these cities by calling ‘unionSet(i, j)’. Finally, the number of provinces will be equal to the number of sets in 'DS’.

  • Create a DisjointSet 'DS’.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’ to create a new set for each city:
    • 'DS.makeSet(V)’
  • Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
    • Run a loop where ‘j’ ranges from ‘i + 1’ to ‘N - 1’ (from ‘i + 1’ to avoid repetition):
      • If ‘roads[i][j]’ is equal to ‘1’, then city ‘i’ and ‘j’ are connected by a road:
        • 'DS.unionSet(i, j)’
  • Return 'DS.getCount()’ as the answer. Here, the ‘getCount’ returns the number of sets in the Disjoint-set.
Time Complexity

O(N^2), where ‘N’ is the number of cities.

 

We create ‘N’ sets (one for each city) in ‘O(N)’. For the ‘unionSet()’ function, the worst-case time complexity is ‘log(N)’, and the amortized time complexity is ‘O(a(N))’, where ‘a()’ is the inverse Ackermann function. As there can be ‘O(N^2)’ roads and we call the ‘unionSet()’ function for each road, the total time complexity is ‘O((N^2)*a(N))’. 

The inverse Ackermann function grows very slowly, and it doesn’t exceed the value ‘4’ for ‘N < 10^600’. So, the time complexity is ‘O(N^2)’.

Space Complexity

O(N), where ‘N’ is the number of cities.

 

As there are ‘N’ elements (one for each city) in the Disjoint-set, we need ‘O(N)’ space.

Code Solution
(100% EXP penalty)
Find the Number of Provinces
Full screen
Console