Description
A tree is a connected, acyclic graph (i.e., no cycles). Describe an algorithm
to determine whether a given undirected graph with n vertices and m edges is
a tree in O(n + m) time.
Hint: be careful when detecting cycles—it’s easy to “detect” cycles that
aren’t actually cycles. You may wish to simulate your algorithm on a two- or
three-vertex tree to make sure it is correct.
