Detect Cycle in a graph

Given a directed graph, find whether it contains cycle or not.
Which is the best algorithm for this problem in terms of memory and time complexity? Assuming the graph can contain approx 1 millions nodes.

3 Likes

<O(N+M),O(N+M)> a simple DFS will do the job.

1 Like

Read this -

 http://www.geeksforgeeks.org/detect-cycle-in-a-graph/ 
11 Likes

I think depth first search (stack based) is better to detect a cycle and memory friendly

Is not what I just said?