How to determine if a undirected graph is a forest in $\mathcal{O}(|V|)$?

Question

So how to determine in $\mathcal{O}(|V|)$ if a graph $G=(V,E)$ is a forest?

Hope somebody has an idea.

Answer 1

If your graph is saved with adjacency lists you can recover the degree of a vertex in constant time. Using this you can check if $e\leq v-1$ in $\mathcal O(v)$ time. If this is not the case then the graph is not a forest.

Now that we know that $e\leq v-1$ we can explicitly look for cycles using dfse's, and since the number of edges is less than $v$ this has complexity $\mathcal O(v)$.