# Number of Provinces problem in Javascript

September 8th, 2021

## Problem

There are `n` cities. Some of them are connected, while some are not. If city `a` is connected directly with the city `b`, and city `b` is connected directly with the city `c`, then city `a` is connected indirectly with city `c`.

province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an `n x n` matrix `isConnected` where `isConnected[i][j] = 1` if the `ith` city and the `jth` city is directly connected, and `isConnected[i][j] = 0` otherwise.

Return the total number of provinces.

## Solution

To find the total number of provinces, we need to find all the cities connected to a particular city `i` to do this, we will loop `n` times that is the size of the matrix. Technically we call it as an adjacent list

Let us consider an example as shown here in figure

Here `1` and `2` cities are connected while city `3` is not, so in this example we can say we have 2 provinces since there are two groups of cities

The adjacent list will look like this

Now we know that city `3` is not connected with either `2` or `1`

whenever there is a break in the connection we need to increment the number of province.

we will be having a loop over the adjacent list and at each point, we will add all the cities in the adjacent list in a queue.

when the queue is empty which indicates we have visited all the connections that are direct or indirect from each city. So that next unvisited site tells us this is a new province

Here is the full code in javascript

``````const findCircleNum = (isConnected) => {
const size = isConnected.length;
const adjList = new Array(size).fill(0).map(() => []);
let provinceCount = 0;
let isVisited = new Array(size).fill(false);
// make a adjacent list visits from each node.
for (let i = 0; i < size; i++) {
for (let j = 0; j < size; j++) {
if (i !== j && isConnected[i][j]) {
}
}
}
const queue = []; // initialising a queue that takes all the cities in a province
for (let a = 0; a < adjList.length; a++) {
if (!isVisited[a]) {
// if not visited then this is a new provinces so count ++
provinceCount++;
} else {
continue;
}
while (queue.length > 0) {
// we will visit all the places that is directly and indirectly connected with a by utilising the queue
const curr = queue.shift();
for (let i = 0; i < curr.length; i++) {
// here we visit all the place directly connected with city a
if (isVisited[curr[i]]) {
// we have alread visited here either its in the queue or its direct connections are already iterated
continue;
} else {