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?