Either breadth-first or depth-first search can be used to identify the connected components of an undirected graph and label each vertex with the identifier of its components. In particular, we can modify the DFS-graph algorithm to increment a counter for the current component number and label each vertex accordingly as it is discovered in DFS.
For directed graphs, there are two distinct notions of connectivity,
leading to algorithms for finding both
weakly connected and strongly connected components.
Both of these can be found in O(n+m) time,
as discussed in Section 
.