Welcome back.
Let's now go ahead and code the solution that we discussed in the previous video.
Now for this we will write a function.
Let's call it count components.
And this function is going to take in n, which is the number of vertices and the edges array.
Now once we are inside this function.
We will first build the adjacency list.
So let's say const graph is equal to build adjacency list which is a helper function that we will write
right.
So build adjacency list.
And then over here we will also pass n and the edges to it.
Now let's just go ahead and write this helper function before we proceed with the main function over
here.
So over here we can say const and the function is build adjacency list.
Now this function also takes in n and the edges.
All right.
Now inside this function let's say const adjacency list.
And let's just make an empty array, an array of arrays.
It's going to be an array of arrays.
And each element is going to be an empty array.
All right.
So and the count of the empty arrays is going to be n.
So we're going to have an array of arrays.
So let me just show that over here.
So this is going to be an array.
And each element is going to be an empty array.
Right.
So something like this.
And the number of empty arrays that we have inside this array is going to be equal to n which is the
number of vertices.
So this is what we're doing over here.
So let's go ahead and we say new array.
And the size is going to be n.
Then we say dot fill with zero.
And then we use the dot map operator.
So dot map.
All right.
So this will give us an array which is which is like this.
And then it will have empty arrays inside it.
Right.
So these are going to be the elements.
So for each of these n elements we're just iterating through the array.
And we are changing it to an empty array.
So this is what we get after this.
Right.
So adjacencylist is just an array of empty arrays at this point.
Now we will just iterate through the edges array which we have passed in over here.
So let's say for.
Let.
Edge of edges.
So we take each value in the edges array which is again an array.
Right.
So we have this for loop.
And then let's just find the first and second element in each of those arrays.
Right.
So the edge will have two nodes u and v as mentioned in the question.
So let's say let node one is equal to edge at index zero.
And let node two is equal to h at index one.
All right.
So this is just like u and v.
So this is u.
This is v as mentioned in the question.
So there is a edge between u and v.
So we identify these two vertices.
Now we are just going to push the respective edge into the correct position in the adjacency list.
So in the adjacency list which at this point is empty at node one.
We are going to push node two right.
So dot push and we're just passing node two.
And we're going to do the same thing at node two also.
So adjacency list at node two we will just push node one.
Now we are doing this because over here this graph is undirected.
So the edge goes both ways.
So that's why we are doing this.
And then we have built the adjacency list.
Now let's just return this.
So return adjacency list.
All right.
So again this is our helper function to build the adjacency list.
So we are back at the count components function.
And over here we have built the adjacency list from the edges and the number of vertices.
Now what we will do is.
We will have a visited object.
So let's say const visited to track whether a vertex is visited or not.
And initially it's going to be an empty object and then we will have a count.
So this count is going to be the number of components.
So we will just go through the graph which is given to us.
And finally we will return this count.
All right.
So this is what we're going to do.
Now.
What we will do is we will just loop through the vertices.
And then if the particular vertex is not visited we will increment count.
And we will call the depth first search function which again will go ahead.
And right now we will call that to traverse the nodes which are connected to that particular node.
So let's go ahead and write this.
So for let vertex.
Is equal to zero and vertex less than n, because there are n vertices, and it's going to be zero if
there are five vertices.
The vertices are going to be zero, one, two, three, four, right.
So for a vertex zero till vertex less than n and then we are just going to say vertex plus plus.
All right.
Now inside this we are going to check if that particular vertex is there in our visited object or not.
So if not.
Visited at vertex.
If it's not visited then we will call the depth first search DFS function right, the depth depth first
search function on that particular vertex, and then we will increment our count.
So we say count plus plus.
So we have identified a new component.
So that's why we are incrementing the count.
And then we are going to write a DFS function.
So we will call that function that helper function to traverse all the nodes which are connected to
that particular vertex.
So we will pass in the graph to this DFS function.
And then we will pass in the vertex.
All right.
And we will also pass in the visited object.
All right, so that's it.
Now we just have to write our DFS helper function.
So let's go ahead and write that over here.
So we can say const DFS.
And this function is going to take in the graph.
And it will take in a particular vertex and it will take in the visited object.
All right.
So this is just a straightforward depth first search which you've already discussed.
So initially we say that visited at the particular vertex we mark it as true.
All right.
Now we're just going to find the neighbors of that particular vertex.
And for this we will use the adjacency list which we are passing to this function.
So const neighbors is equal to graph.
At vertex.
And over here this graph is the adjacency list which you are passing.
Right.
So graph is the adjacency list.
And we are passing it over here.
So over here we are getting the adjacency list.
And we are going to that particular key value or.
All right.
So in that again this is an array.
So we are going to that particular index in the array.
And then we are getting back an array.
Right.
We have seen that this is an array of arrays.
So neighbors now will be an array which represents the uh neighbors of that particular vertex.
Now we have the neighbors.
Now we are just going to loop through the neighbors.
And if we see that any of the neighbors is not visited, then we are just going to call recursively
the DFS function on that particular vertex.
So let's go ahead and do that.
So for let.
I is equal to zero I less than neighbors dot length.
I plus plus.
Now inside this we are going to check the neighbor whether that particular neighbor is visited or not.
So just to make our code neat, let's have const neighbor over here, which is equal to neighbors at
I.
So this is a particular neighbor.
All right.
Now we are going to check if this is visited.
So if not visited at neighbor.
So if that particular vertex is not yet visited then we will call DFS recursively on that vertex.
Right.
So DFS again we are passing the graph.
We are passing that particular neighbor and we are passing the visited object.
That's it.
So this is our depth first search uh helper function.
Right.
So once we are out of this we will have visited all the neighbors of that particular vertex.
Right.
So again this is how we are identifying the components.
So when we call the DFS function all the vertices which are connected to it or which are part of that
particular component will be visited.
So we will again call DFS only when we see a vertex which is not yet visited.
So that is what we are doing over here.
All right.
So this is our code.
So we are done with the function.
Now let's go ahead and test it.
Now for this let's take an example for example let's say n n is equal to five.
So let's say const n is equal to five.
So we have the nodes 0123 and four.
And then let's have an edges array.
So const edges.
Let's say this is an array of arrays.
Let's say there is a link between 0 and 1.
And let's say there is a link between.
One and two.
And there is a link between 2 and 3.
And let's say there is nothing connected to four.
So our expectation is that we should get two right?
The answer should be two.
So let's call our function and test it out.
And we're going to pass in N and the edges over here.
And let's just run our code and take a look at the output.
All right.
So yes, you can see we have the answer as two.
Right.
So this is correct.
Why is that.
So we have zero and one connected.
Let me just draw this out over here.
We'll just take a few test cases and draw it out over here so that we are very thorough.
And then we will take a sample input and walk through the code to understand what's happening in greater
depth.
All right.
So let's take a look.
So there is a link between 0 and 1.
And there is a link between 1 and 2.
And there is a link between 2 and 3.
And then we have n equal to five.
So these are our vertices.
So there is no link between four and anything.
So this is how our graph looks like.
So we can see clearly there are two components.
So this is one component and this is the second component.
That's why we have our answer two over here.
Now let's take another example.
So let's just delete this and let's take another example.
So for example I say there is a connection between 0 and 1 one and two.
And let's say there is a connection between 3 and 4.
All right.
So again and then let's increment n.
So let's make n is equal to seven.
So I'm just changing the example.
So we have values till six.
So 0 to 6.
These are our nodes.
Now let's say there is also a connection between 5 and 6.
All right, now let's go ahead and run our code.
And you can see we have three components.
Let's try to draw this out.
So we have a connection between 0 and 1.
There is a connection between 1 and 2.
There is a connection between 3 and 4.
And there is a connection between 5 and 6.
So yes.
So this is component one.
This is component two and this is component three.
All right.
So yes three is correct.
Now let's take this example.
And let's just walk through the code and see what's happening.
So we call the count components function and we are passing n is equal to seven.
And we are passing this edges array over here.
All right.
So these connections.
So once we are inside the function over here first we are building the adjacency list.
So we come to the build adjacency list over here.
All right.
So let's see what's happening over here.
Let's just draw it.
So in this part of the code we are having an array of empty arrays.
And over here this will have elements equal to n and n is equal to seven.
So this is going to look like this right.
So we are going to have seven empty arrays.
Let me just, uh, draw this a bit different so that it's easy to visualize.
So we have.
The first empty array over here.
The second empty array over here.
The third empty array over here.
The fourth empty array.
Fifth empty array.
Sixth empty array.
And seventh empty array.
So this is how adjacency list is going to look at this point.
Then we are just going to loop through the edges array right.
So again let's take a look at our edges array.
It's looking like this right now.
For each of these, we are going to take this as node one and this as node two.
So that is happening over here.
And then we are going to push node two into node one at the adjacency list.
So let's just do it for one example.
So we have zero one over here.
All right.
So this is this link over here zero one.
So node one let me just take a pen.
This is going to be node one.
This is going to be node two.
So adjacency list at node one.
So this index over here is one right.
So this is zero.
This is one this is two this is three this is four this is five this is six.
The indices.
So at one right.
So at zero this is the index right.
So at zero we are going to insert node two which is one.
So over here we are going to insert one.
So this means means there is a link between 0 and 1.
And because this is an undirected graph we are also pushing node one at node two.
So node two is one.
So index one.
And we are pushing node one which is zero right.
So we are getting zero over here as well.
So this is what we're doing then when we take this link.
So at index one we are going to push two.
And at index two we are going to push one.
All right.
And then when we take index three we are going to push four.
And at index four we are going to push three.
And at index five we are going to push six.
And at index six we are going to push the value five.
So this is how our adjacency list is going to look like.
All right.
So let me just make some space over here and clean this up a bit.
Now we got our adjacency list.
And we are back in our main function which is count components.
So this graph over here is this adjacency list at this point.
Now we have the visited object which is empty at this point.
So let me just write that over here.
So we have the visited object.
And this is empty.
All right.
Now over here, count is equal to zero.
So count at this point is equal to zero.
Then we come over here.
Now we are going to take the values.
Vertex is going to take the values zero to less than n n is equal to seven.
So it's going to take the values 0123456.
Right.
All right.
So initially it's zero.
Now we are checking whether the vertex zero is visited.
We see that it's not visited right.
So we come inside.
We increment the count.
So count becomes one.
And then we are calling the DFS function where we are passing the vertex zero.
So vertex is zero.
Now let's see what's happening.
We come to the DFS function.
All right.
So let's go there.
So this is our DFS function.
So let me just clean this up a bit.
All right.
So we are over here and we have called this function and vertex zero is passed to it.
All right.
So vertex zero this adjacency list and the visited object is passed.
So we mark the particular vertex which is vertex zero.
True.
So we have zero true over here in our visited object.
And then we are going to take the neighbors of zero right.
So the neighbors of zero are just one.
So there's just one neighbor.
And then for I is equal to zero I less than one.
So it's just going to iterate.
One time we are going to take the neighbor at index zero which is one itself.
And then we are checking whether one is visited.
We see that it's not visited.
So we are going to call the depth first search on vertex one.
So again we come inside and over here we mark one visited.
So we say one true.
And then we are going to take the neighbors of one which is zero and one, right?
So neighbors is going to be these two.
This array is neighbors at this point.
The length of it is two.
So I initially is going to take zero.
And we are going to take the neighbor at index zero which is zero.
We see that it is already visited right.
It's already visited.
So we don't call DFS for it.
And I increments to one and one is less than two.
So we come inside and at index one the neighbor is this one over here.
Right.
This is zero.
This is index one.
So we get two.
And then we check whether two is visited two is not visited.
So we call the DFS function recursively and we pass the vertex two.
So we come again inside.
Over here we mark two as visited.
So two is visited.
So we have visited at two is marked as true.
And then we are going to check the neighbors of two which is just one.
And one is already visited over here.
So we are not going to call the DFS function over here.
So you can see that at this point all of these zero, one and two have been marked as visited.
All right.
So let's come back to our main function.
So this was part of the call where we called this for zero.
Right.
So let me just clean this up a bit.
So this was when vertex is equal to zero.
So in in this case by doing DFS we went from 0 to 1 and from 1 to 2.
So all of these have been marked as visited.
Now when we are out of this vertex is going to increment to one.
And we come over here and we see that one is already visited.
So we don't call DFS for one.
And this is incremented to two.
And when we come to two we see that this is also visited.
So we don't call DFS for two.
This is incremented to three.
And when we come to three we see that this is not visited.
So we will increment the count.
So count becomes two and then we will call DFS and we will pass three.
So the vertex at that point is going to be three.
And then when we come to three we will mark three as visited.
Right.
So three true.
So that's going to happen over here in the DFS function.
Right.
So we have seen that we have we mark here visited true.
Let's just clean this up.
All right.
So over here three is marked as true.
And then we take the neighbors of three which is just four.
And then DFS is called on it.
So this is also marked as true.
So four is also visited.
And then we come out of this.
So when we come back over here, vertex was three and then it's incremented to four.
But when it gets to four we see it's already visited.
So it does not come inside over here.
And then it changes to five.
And when we look at five this is not visited.
So we increment the count.
So we get three over here and we call the DFS with five.
Right.
So again inside the DFS this is going to get marked as visited.
And we will call DFS on its neighbor which is six and six is not visited.
So this is also marked as visited.
And we come out of it.
Right.
So this was when vertex is five.
So we are out again over here vertex is incremented to six.
But at this point we see that six is already visited.
So we don't call DFS for six and we are done.
So we come out and we're just going to return the count which is equal to three.
So this is how this function works.
All right.
So we have seen how this works.
Now let's take a quick look at the space and time complexity of this solution.
So let me just clear this up.
So this is the function that we have written.
Now let's take a look at the complexity analysis.
So first let's take a look at this time complexity.
So what's the time complexity of this solution.
Let's take a look at the places where we have operations which will scale when the input will scale.
So over here we are building the adjacency list right.
So let's go to that part of the code.
All right.
So that's happening in this function right now.
What is the number of operations that we are going to do over here?
Right.
So to build the empty adjacency list initially we are going to do v number of operations.
Right.
Because over here v or n is the number of vertices, n is the number of vertices v is also typically
we use the word the letter v for the number of vertices.
So over here we are building an empty array with v elements which are all empty right.
Empty arrays.
So over here we are going to do v operations because we have to loop through the array.
And then we have to create these empty arrays over there.
Right.
So over here we have V operations.
And then over here we are going to loop through the edges right.
So we have this for loop.
And let's say the edges is e.
The number of edges is e.
So over here again we are doing E operations because one operation per edge.
So we can see that the build adjacency list function is going to do v plus e operations.
Over here we have v plus e operations.
And then let's come back to our main function.
So over here also you can see that we are looping through all the vertices, right.
We are looping through all the vertices at this point.
So this is going to be v operations.
And then we are going to call the DFS function right.
The DFS function on the neighbors which are not visited yet.
So again this over here is going to happen e number of times.
Right.
So let's take an example.
Let's see let's for example take a graph where zero is connected to one which is connected to two.
And then let's say three is connected to four which is connected to five.
And at this point n is equal to six, or the number of vertices is equal to six.
Now over here what will happen.
Let's just trace this to understand that this also is actually v plus e.
We are taking the vertices from 0 to 5 right.
So that's going to be five operations.
So let me just write that over here which is equal to v number of operations.
So we see that zero is not visited.
So a DFS call is made for this.
So let me just write a tick mark over here.
And then we come inside the DFS function.
So let's see what happens over there inside the DFS function over here you can see we have this loop
where we go through its edges.
Right.
So if this one over here has even edges right.
So we will be doing even operations over here over here right in this for loop.
Now let's go ahead.
So we are going to call DFS recursively on edge one because it's not visited right.
So at that point we are making a call a DFS call over here.
So let me write a tick mark over here.
And then when we are again inside this for this vertex we will make E two number of operations in this
for loop where e two is the number of edges of this particular node.
All right.
So in this case we are going to go to two only because there is just one unvisited which is two right.
But again it's going to do two operations because we are going to check if zero is visited.
We will see it's visited.
So we don't do an operation over here.
And then we go to two.
So let me write a tick mark over here recursively.
We are again calling the DFS function with vertex two.
And then once we are inside this we are going to have operations equal to the number of edges of this
node over here, which just let me just write it as E three.
So in this case it's just one and one is already visited.
So we don't recursively call anything and we come out.
So this is the total number of operations that we have so far done.
Now let's come back to our main function.
So we are over here.
So we have done.
At that point vertex was equal to zero.
Now we go to vertex is equal to one.
We see it's already visited.
So we go ahead and we come to two that's already visited.
So then we come to three.
So when we come to three we see it's not visited.
So we are going to make a call on vertex three.
Again we come inside the DFS over here right again the DFS function which you've written over here.
And at that point let me just write over here.
We're going to make E for number of operations in this for loop where E4 is the number of edges with
three.
In this case it's just one.
So we are recursively calling the DFS function for this particular node over here.
Again we will do E5 operations where e5 is the number of edges of this node.
And over here again we will visit the fifth vertex right if vertex five.
And over here also let me say we are doing E6 operations in this for loop for that case.
Now once we are out of this, we are back over here and then we will just go through four and five and
we see that these are visited and we are out.
So this is the total number of operations that's happening in this case.
Now let's try to analyze this.
How many operations are there.
If we add up all of this right.
If we add up all of these, we will see that we will get two into total number of edges.
Because this is an undirected graph.
So an edge between 0 and 1 will be counted for zero and as well as one.
So that's why it will be two times the number of edges.
Over here we are doing operations equal to two into the number of edges.
So this is happening inside our DFS function.
And then you can see over here we are doing vertex number of operations right.
The number of operations because we are calling the over here.
This for loop over here is actually going through each of these particular nodes.
So we can see that in this place along with the DFS function we are doing a total of V plus two v operations.
And again we have seen that in the case of building the adjacency list we are doing V plus E operations.
So that's why we can say that the time complexity of this solution is of the order of V plus E.
Again this constant can be neglected and we are getting v plus e over here as well as here.
So the time complexity of this solution is equal to v plus e.
Now what about the space complexity.
So let me just clear this up.
And I'm just writing it again.
The time complexity of the solution is of the order of V plus e.
Now what about the space complexity?
We have seen that the things that take up space are the adjacency list which we are building.
So that's the first thing.
Then we have a visited object that takes up space.
And then because we have written this solution recursively.
So we are going to take up space on the call stack.
So these are the three things that can take up space or auxiliary space.
Now the adjacency list is going to have the vertices and the edges right.
So this is going to take space of the order of v plus e.
So we will have v number of arrays.
And in each of these arrays right the edges would be represented.
So that's why the space which is taken up by the adjacency list will be of the order of V plus e.
So that's pretty straightforward.
Now the visited object every vertex is going to be there.
Finally in the visited object right once we have completed it.
So this is going to take space of the order of V where v is the number of vertices, and then the call
stack.
In the worst case, if all the vertices are connected, the call stack can take up space of the order
of V, because that's the maximum number of calls on the call stack, which can be there on the call
stack at the same time.
So we can see that based on this, the space complexity is going to be of the order of V plus E.