Let's assume connected graphs only (you probably want to ask the interviewer if you can assume this btw). The solutions below are O(V+E). The directed case walk is a little easier due to the explicit direction of edges, although the undirected case does have a nice short-circuit check if the graph is even remotely dense. There is no short-circuit check for general directed cases. Directed graph: It has a cycle if a DFS walk encounters any vertex V with an incident edge E which connects to another vertex that has already been visited (a back edge). Undirected graph: It has a cycle if |E| >= |V| (the # of edges is at least the # of vertices, because then it can't be a simple tree which any undirected acyclic graph must be). Or if that passes, then DFS walk and for each unvisited vertex V, record parent[V] as the preceding vertex that led to it. It has a cycle if any edge E incident from V connects to another vertex that (a) is already visited and (b) is not parent[V].