# Connected Components in an undirected graph

Given a connected undirected graph. Perform a Depth First Traversal of the graph.

Example 1:

```
there are 3 connected components in the above undirected graph
1-2-3
4
5-6
```

**method:**

1) Initialize all vertices as not visited.

in** dfs **function for every vertex 'v',if 'v' is not visited before, call **dfsui(v)**

2)in **dfsui(v)**,Mark 'v' as visited.

for every adjacent 'u' of 'v',

If 'u' is not visited, then recursively call **dfsui(u)** ,

if adjacent nodes exit than it goes recursively ,

once the adjacent nodes are not there it comes out of** dfsui() **

and goes back to** dfs() **which describes that it was one of the connected component.

now in **dfs **we increment the counter and again every vertex 'v' is checked again.

**c++ implementation:**

void dfsui(int source, vector<int> g[], bool vis[]) { vis[source] = true; for(auto i:g[source]) { if(!vis[i]) dfsui(i, g, vis); } } int dfs(vector<int> g[], int N) { bool vis[N]; int c=0; for(int i=0;i<N;i++) vis[i]=0; int k; for(k=0;k<N;k++) {if(vis[k]==0){dfsui(k,g,vis);c++;} }return c; }

**Time complexity:**O(V + E), where V is the number of vertices and E is the number of edges in the graph.**Space Complexity :**O(V).

Since an extra visited array is needed of size V.