Hi everyone, let's do this question.
You are given a graph with n vertices to indicate the connections in the graph.
You are given an array of edges whose each element is an array of the form u comma v u v indicates that
there is an edge between u and v, where u and v denote two vertices or nodes.
Write a function that takes in n and the edges array, and returns the number of connected components
in the graph.
So this is the question over here we are given n vertices.
So we will be given this number n.
All right.
And then we will be given an edges array.
So for example if n is equal to four and the edges array which is given to us is this over here.
So this indicates there is an edge between 0 and 1.
So there is another edge between 3 and 1.
And there is an edge between 1 and 2.
Now because n is equal to four the edges are zero.
The vertices are zero, one, two and three.
All right.
So these are the four vertices.
And over here this edges array gives the connections between these vertices.
So let's draw this out.
So we have a connection between 0 and 1 which is this over here.
So that's this link.
Then there is a connection between 3 and 1 which is this link over here.
And then there is a connection between 1 and 2 which is this link over here.
And again this is an undirected graph.
All right.
So over here if this is the graph which is given to us, we can see that all of these nodes are connected
to each other.
Therefore this makes up just one component.
So the number of components in this case is equal to one.
Now let's say n is equal to four.
And the array which is given to us the edges array is this one over here, which indicates there is
a connection between 0 and 1.
And there is a connection between 2 and 3.
So because n is equal to four the vertices are zero one, two and three.
And we can see that the connections are between 0 and 1 which is indicated by this array over here.
And then there is a connection between 2 and 3 which is this connection over here.
Now in this case we can see that this is one component and this is another component right.
So these are not connected with each other.
So if this was the edges array and n is equal to four then this function should return the number of
components as equal to two which is.
This is one component and this is the second component.
All right.
So we have understood this question.
Now let's go ahead and try to think about how we can solve this question.
Now for this let's say that this is the graph which is given to us.
So in this case n would be equal to seven.
So that's why the vertices are zero, one, two three, four, five and six.
So n would be equal to seven.
And then each of these connections would be mentioned in the edges array.
Now before we proceed and think about how to solve this question, let's try to make a few observations.
The first observation is that let's for example, take this node.
And if you call if you do a breadth first traversal or a depth first traversal starting from this node,
then you can notice that we would visit all these nodes which are connected to it.
Right.
So you can do either breadth first search or DFS or depth first search.
Right.
So this is just traversing.
Right.
We have seen BFS or DFS is a method to traverse a graph.
So if we call BFS or DFS which we already discussed with this node, then all of these nodes would also
be visited.
Right.
We would traverse this node, this node, this node and this node.
So it's it's we can do it in either way because these are connected.
So this is the first observation right.
So let's say the graph was something like this.
So if all of them are connected then if we just call BFS or DFS with any of these nodes we would visit
all these nodes.
Right.
So that's the first observation.
So if we call BFS or DFS that is breadth first search or traversal or depth first search or traversal
on any node.
Then we can visit all the nodes which are connected to it.
All right.
So this is an interesting observation.
Now let's say this is the graph which is given to us.
If we just do BFS or DFS on this particular node, then the second observation is that we would not
be visiting this node, and we will not be visiting these two nodes because they are not connected to
this node.
Right.
So that's the second observation.
The first was that if we call BFS or DFS on this node, everything that is connected to it will be visited.
And the second thing is that everything that is not connected to it will not be visited.
So these are the two important things that we should notice over here.
Now let's see how we can solve this question.
We just have to iterate from 0 to 6 right from the nodes 0 to 6.
And we can just call BFS or DFS if that particular node is not yet visited.
So this will ensure that we will also visit the unconnected parts.
So for example when we call BFS or DFS with node zero we have seen all these will be visited.
And when we call BFS or DFS with two this one will be visited.
And when we call it with 4 or 6 these two will be visited.
Right?
So whenever we see a non visited node all we have to do.
We have to mark it as visited and we can increment the count because we are seeing a new component,
right?
So let's try to trace this and think about this algorithm.
So we are going to iterate from the nodes 0 to 6.
So we have 0 to 6 over here.
Now initially the count of the number of components is set to zero.
All right.
Now let's say we call DFS.
Let's try to solve this question with DFS.
Now again we can solve it in either way.
But in this video let's just solve it with DFS.
All right.
And let's try to do it in a recursive manner.
Now let's say we are calling the DFS function with node zero.
So at that point we will visit 013 and five.
So these will be visited.
Now again when we come to one when we are iterating from 0 to 6 right.
So after zero we come to one.
At that point we will see that it is visited.
So we will not call DFS on that node.
All right.
And again once we visited these we got one component.
So this is one component.
So that's why the count has been incremented to one.
All right.
So zero is done.
Now we came to one over here we see one is already visited.
So we don't go inside.
We don't call DFS.
We again increment.
We come to two.
We see that two is not yet visited right.
So we will call the DFS function on two.
And we will increment the count because we are having a new component now because it does not have any
neighbors, it will not go to any other node.
All right.
But this one over here is visited and this is the second component.
Now we again proceed to three.
And at that point we see that this is already visited.
So we don't call DFS.
On node three we proceed to four right.
So we proceed to four.
Now when we call DFS on four, four and six are going to be visited.
Right.
So four and six are visited and our count is changed to three.
Then we come over here, we come to five.
We see it's already visited.
Then we come to six.
We see it's already visited.
And that brings us to the end.
And we have identified that the number of components is equal to three.
So this is one component.
This is the second component.
And this over here is the third component of this graph.
All right.
So this is how we can solve this question.
Now let's try to look at the complexity analysis of this question.
First let's try to think about the time complexity of this solution.
Now what are the things that take up time over here or number of operations.
Right.
So we will have to build the adjacency list right.
So we will be given just the edges array.
So in this case the edges array will be zero comma one which is this link.
Then one comma three.
And then we have three comma five.
And then we have this two which does not have anything.
So there is no edge.
And then we have four comma six.
So these are the elements in the edges array.
Now using n which is equal to seven in this place.
And this edges array we will have to build the adjacency list.
Right.
So why is this required.
This will be required for doing our DFS right.
So whenever we come over here and we do the depth first search.
And again you could do BFS also.
Now when we in this question we are just using DFS.
Now when we do this we will be using the adjacency list to identify the neighbors.
Right.
So we will have to build the adjacency list.
Now building the adjacency list from the edges array over here.
And the vertices is going to be an O of v plus e where v is the number of vertices and e is the number
of edges.
Operation.
Right.
So initially we are going to build an empty adjacency list.
So it's going to have n number of elements.
So in this case n is equal to seven.
So that would be seven empty arrays right.
So it would be an array where each element is an empty array.
And there will be seven such empty arrays.
So building this is going to be a V operation because this is going to have v empty arrays over here.
All right.
So this is the empty arrays.
And then we have to loop through each element.
So this has the number of elements over here will be equal to the number of edges.
So we will do e number of operations to loop through the edges array over here.
Right.
So that is this e over here.
And then we will just push into zero over here.
We will push one and into one we will push zero.
And in this way we will go ahead and build the edges into these elements in their respective places.
So to build the adjacency list we will have to do O of V plus E operations.
So this is one thing that takes up time.
Now what else.
What else takes up time.
You can see that looping through the vertices that is going from 0 to 6, and then calling DFS recursively
will also take some number of operations.
Right.
Let's try to think about this.
So this part over here will take O of V plus E operations.
Why is that.
So let's try to think about it over here we have this sample graph right.
So initially when we call the DFS when we go from 0 to 6 you can see straightforward over here we are
going to have v number of operations.
And then we are trying we are going to have e number of E one operations for node zero.
Right.
So when we call DFS for zero let me just write that over here 012345 and six.
So when we call DFS for zero we will come inside the DFS function.
We will look at its neighbors right.
So we will try to see each of its neighbors each of its edges if it's visited or not.
So that would be E one operations where E1 is the number of edges of zero.
Similarly, when we call DFS for node one again we are going to do e two operations inside the DFS function.
When we call DFS for two, we are going to do E three operations, etc..
Right.
And we are going to call the depth first search function for each of these nodes.
So that is what we're doing over here right.
We are iterating.
And then we are going to call the DFS function for each node.
Now every node will be called DFS will be called once with every node.
It can happen in two ways.
The first way is like if it's not connected for example two, right?
Two will be called when we get to two over here.
Now DFS on one, three and five will be called recursively.
When we call it for zero it will call it for one as well.
And from there it will call it for three as well.
And from there it will call it for five as well.
So DFS for each of these nodes will happen.
Whenever it happens.
We will have inside that function e I times of operations.
Right.
So in this case there will be e four operations over here E five operations over here E six operations.
And over here E seven operations.
Because we have to iterate through the neighbors of that particular node, which will be an array.
Right.
So that would be received from our adjacency list.
So for example in this case let's take the three right.
So this is this is zero.
This is one this is two this is three etc..
So I'm just taking the example of three.
In the case of three the neighbors are one and five.
This is three right.
So one and five will be there over here.
So whenever we are doing DFS on three we will be taking its neighbors which are one and five.
And then E four.
Over here will be two operations.
We because we have to check whether one is visited.
If not we have to call DFS on one and we have to check whether five is visited.
And if not we have to call DFS on one.
So that would be two operations over there.
So you can see that the total number of operations over here will be in this case.
That's the number of operations.
And if we add all of these up together we will get two times E because this is an undirected graph right.
So an edge between 1 and 3 will be represented over here as well as over here.
This is for one right.
So over here also we will have zero and three.
So this three over here this indicates the connection between 1 and 3.
And this one indicates the connection between 1 and 3.
So because this is an undirected graph, if we add up all of these together we will get two times e.
That's why we can see over here we are getting o of v plus two e number of operations.
And this is just a constant.
So we can avoid this.
And we can see that to iterate through the vertices and recursively call DFS, we are doing a total
number of O of v plus e operations.
So let me just clear this up again.
How did we get this over here.
It's just the total right o of V plus one and uh v two plus E two etc..
Right.
So this has to happen for each node.
So we have seen that and this will converge to O of v plus e.
Again we have to but that can be just removed because that's a constant.
So we can see that the time complexity of this solution is of the order of v plus e, where v is the
number of vertices and e is the total number of edges.
Now what about the space complexity of this solution?
Now for this, let's try to think about the things that take up space which can scale when the input
increases.
So we have the adjacency list which we have to build.
Then we have the visited object.
And then because we are implementing this solution over here in the DFS method, by using DFS and in
the recursive manner, we will have space on the call stack.
Now what about the adjacency list.
So the adjacency list will have v number of arrays right.
So it's going to be an array of arrays.
And the arrays inside this array is going to be equal to number of the vertices.
Right.
One array for each vertex.
And then inside these we will have elements which represents the number of edges.
So that's why we can see that the space that is taken by the adjacency list will be of the order of
v plus e, right.
So v number of arrays and inside the arrays elements to represent the edges.
So over here this takes order of v plus e space.
And the visited object is going to take space of the order of V because we will finally have all the
vertices visited.
Right.
So we will just have one entry for one vertex.
That's why this is going to take space of the order of V and the call stack.
In the worst case, if all the nodes are connected, then because we're doing a recursive solution we
call stack maximum can have v call calls in the call stack at the same time.
So these are the things that take up space.
And we have seen the order of space that these things take up.
So that's why we can say that this is the greatest.
So the space complexity of this solution is going to be of the order of V plus E.