Here is how to count connected components:
function countComponents(n, adj):
visited = [false] * (n + 1)
count = 0
for i from 1 to n:
if not visited[i]:
count = count + 1
dfs(i)
return count
function dfs(u):
visited[u] = true
for each v in adj[u]:
if not visited[v]:
dfs(v)
Loop through all vertices from to . For each vertex , if it is not visited yet, increment count and run DFS from . The DFS marks all vertices in that component.
Each DFS call finds one complete component. The number of DFS calls equals the number of components.
This runs in time and uses space.