September 8th, 2021

Link to leetcode

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`

.

A 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*.

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]) {
adjList[i].push(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;
}
queue.push(adjList[a]); // push the adjacent list at the current province
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 {
queue.push(adjList[curr[i]]);
isVisited[curr[i]] = true; // store all the places that we visited
}
}
}
}
return provinceCount;
};
```