Welcome back, dear reader. So, how is it going with the graphs data structure. We hope that you are enjoying it as much as we are. So, let us now move to this problem called Get Connected Components.

**Important Links :** Problem Link, Solution Video

We are given two integers: the first represents the number of vertices of the graph and the second represents the number of edges of the graph. Then, we are given the Edges of the graph in the form of source-neighbor-weight triplets. We have to find the connected components of the graph and return them in the form of an ArrayList of ArrayList. For instance, have a look at the image shown below:

So, in this graph, we had three connected components and we filled the vertices of each connected component in a separate ArrayList and put all the ArrayLists in one ArrayList. We recommend you refer to the problem video (0:00-1:25) to understand the question and clear your doubts regarding it in detail.

So, let us see the procedure that we have to follow. Consider the graph shown below:

**Let's first take a look at hasPath function code:**

We have taken an example graph for which we will fill the connected components. The prerequisite for this problem is the Has Path Problem where we learnt how to apply DFS on a graph.

Let us understand the procedure in a nutshell:

- We will apply DFS for
**every unvisited vertex**of the graph. - While we encounter any vertex that has not already been visited, we will mark it visited and add it to the ArrayList.
- Once we complete the traversal of one component, we will add that component's arraylist to our answer ArrayList of ArrayList.

So, let's start implementing this procedure. Let us start from the first vertex i.e. vertex 0. We will create a new arraylist as we are going to traverse a new component. Now, we are at vertex 0. We will mark it visited and then add it to the new ArrayList that we have created. Then, by applying DFS, we will reach its neighboring vertex. Since the only neighbor of vertex 0 is 1, we will reach vertex 1.

Repeat the same steps as above i.e. add the vertex to the component ArrayList and mark it visited. Now, 1 has only one neighbor i.e. vertex 0 and it is already visited. So, we can not go there. Since there is no more neighboring vertex to visit, this component is complete and we will add this component's ArrayList to our answer ArrayList of ArrayList as shown below:

We move to the next vertex i.e. vertex 2. Since this vertex is not visited, we apply DFS on it and create a new ArrayList as we are traversing into a new component.

**Note:**We get to know that we are traversing a new component as after traversing 0 and 1, we did not have any neighbor to traverse to but there are a total of 7 vertices in the graph numbered 0-6. This means that 0 and 1 were part of one connected component that is not connected to the rest of the graph.

Now, let us move at vertex 5. Here again, we have created a new ArrayList and in that ArrayList, we have added 5 and marked it as visited.

Now that we have applied DFS on all the vertices, we have got our answer. This is how we will find the connected components of a graph.

Dear reader, we recommend you refer to the solution video to understand the complete solution.

java; true";

So, dear reader, we recommend you refer to the solution video ( onwards) to understand the above code completely and also clear all your doubts regarding the same.

Now that we have completed the discussion on the code and the procedure, let us analyze the time and space complexity of the code.

The time complexity of the above code is O(V) as we are going to visit every vertex exactly once.

The space complexity of the above code is O(h) where h is the height of the recursion stack.

So, dear reader, we hope that you have understood everything completely. We recommend you watch the complete solution video once to understand the concept once completely. With this, we have completed our discussion of this problem.

Here are a few suggestions from our side that you do not want to miss:

- We recommend you solve the Has Path and Print all Paths problems first before coming to this problem as it will help you get a good grasp on the DFS of a graph.
- We also suggest that you do this hard work of drawing the Euler tree every time as it will help you get a good insight of the dry run of the recursive code in Graphs. So, keep practicing and working hard. Till then, Happy Coding!!!