Finding connected components

Statement

An undirected graph $G$ with $n$ vertices and $m$ edges is given. It is required to find all connected components in it — groups of vertices such that within a group from each vertex one can reach any other, and between different groups no path exists.

Solution

To solve this problem, you can use DFS or BFS.

In fact, we perform a series of DFS/BFS runs:

the first run starts from the first vertex and finds all vertices of the first connected component;
then we take the first not yet visited vertex and start a traversal from it — thus we find the second component;
and so on, until all vertices have been visited.

Total running time of the algorithm: $O(n + m)$ .