Counting Components - Algorithm

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 $1$ to $n$. For each vertex $i$, if it is not visited yet, increment count and run DFS from $i$. 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 $O(V + E)$ time and uses $O(V)$ space.