Give an algorithm that determines whether or not a given undirected graph G=(V,E) contains a cycle. Your algorithm should run in $O(V)$ time, independent of E.

**Solution:**

If there’s a back edge, there’s a cycle. If there’s no back edge, there are only tree edges. Hence, the graph is acyclic.

Thus, we can run DFS: if we find a back edge, there’s a cycle.

**My doubt is how to manage this in $O(V)$ time ? **