Algorithms: Design and Analysis, Part 1 - Exam Question 11

Problem:

Which of the following statements hold? (As usual n and m denote the number of vertices and edges, respectively, of a graph.) [Check all that apply.]

Solution:

Breadth-first search can be used to compute the connected components of an undirected graph in $O(m+n)$ time.
Depth-first search can be used to compute the strongly connected components of a directed graph in $O(m+n)$ time.
Breadth-first search can be used to compute shortest paths in $O(m+n)$ time (when every edge has unit length).
Depth-first search can be used to compute a topological ordering of a directed acyclic graph in $O(m+n)$ time.

All of these options are correct and all of them are just standard results.