Last Updated: 1 Apr, 2021

Find the Number of Provinces

Moderate

Asked in companies

Solve now

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’.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

Consider the given city network as an undirected graph. So, the number of provinces is equal to the number of connected components in the graph. We can find the connected components by performing a Breadth-first search (BFS) traversal starting from every unvisited node. Each BFS traversal will mark each node in a connected component as visited, so the number of connected components is equal to BFS traversals.

Create an array 'VISITED[N]’ set to ‘0’. Initially, all nodes are unvisited.
Initialize an integer 'COUNT = 0’ to count the number of BFS traversals.
Use a queue ‘BFS_Q’ to perform the BFS traversal.
Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
- If 'VISITED[i]’ is equal to ‘0’:
  - ‘BFS_Q.push(i)’
  - Run a loop while ‘BFS_Q’ is not empty:
    - ‘V = BFS_Q.pop()’
    - 'VISITED[V] = 1’. Mark node ‘V’ as visited.
    - Run a loop where ‘j’ ranges from ‘0’ to ‘N - 1’:
      - If ‘ROADS[V][j] = 1’ and 'VISITED[j] = 0’, then nodes ‘j’ is connected to ‘V’ and is unvisited:
        ‘BFS_Q.push(j)’
  - 'COUNT += 1’. Increment 'COUNT’ for each unvisited node.
Return 'COUNT’ as the answer.

Solve now

03 Approach

Consider the given city network as an undirected graph. So, the number of provinces is equal to the number of connected components in the graph. We can find the connected components by performing a Depth-first search (DFS) traversal starting from every unvisited node. Each DFS traversal will mark each node in a connected component as visited, so the number of connected components is equal to the number of DFS traversals.

Create an array ‘VISITED[N]’ set to ‘0’. Initially, all nodes are unvisited.
Initialize an integer 'COUNT = 0’ to count the number of DFS traversals.
Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
- If ‘VISITED[i]’ is equal to ‘0’:
  - ‘dfs(i)’. Traverse all nodes connected to ‘i’ and mark them as visited.
  - 'COUNT += 1’
Return 'COUNT' as the answer.

The ‘dfs(integer V)’ function:

‘VISITED[V] = 1’. Set the node ‘V’ as visited.
Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
- If ‘ROADS[V][i] = 1’ and ‘VISITED[i] = 0’, then:
  - ‘dfs(i)’.

Solve now