184. Detect a Cycle in a Directed Graph

Given a directed graph with n vertices and m edges, print 'Yes' if it contains a cycle, otherwise 'No'.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, a directed edge from u to v. Output: Print 'Yes' if the directed graph contains a cycle, otherwise print 'No'.

1 <= n <= 10^5

The 'on recursion stack' tracking must be CLEARED once a vertex's DFS call fully returns (marking it merely 'visited' but no longer 'on-stack') - forgetting to clear this is a common bug that would incorrectly flag non-cyclic graphs as having cycles.

Check whether a directed graph contains a cycle. Brute force: Try to trace every possible directed path exhaustively looking for one that returns to its own starting point - this is far more work than a single DFS pass with proper on-stack tracking. Optimised: Distinguishing 'currently on the recursion stack' (still being actively explored) from 'fully finished' (already completely processed and popped) is the crucial detail for DIRECTED graphs - a back-edge to a FINISHED vertex is perfectly fine (it just means multiple paths converge there), but a back-edge to an ON-STACK vertex means you've looped back to an ancestor, which is exactly a cycle.

For every vertex, run a fresh DFS or BFS restricted to following directed edges and check whether that traversal can ever come back to reach the starting vertex itself. If any vertex can reach itself this way, the graph contains a cycle. This works because a directed cycle is exactly a path from some vertex back to itself, but repeating a full traversal from every vertex is wasteful since most of the graph gets re-explored many times. Time: O(n * (n + m)) Space: O(n)

Do one DFS over the whole graph, marking each vertex as unvisited (white), currently on the recursion stack (gray), or fully finished (black). While exploring from a vertex, if you ever follow an edge into a vertex that is currently gray, that's a back edge to an ancestor, which means a cycle exists. This single pass visits every vertex and edge exactly once, which is asymptotically the same cost as the BFS version but needs no explicit in-degree bookkeeping and is the standard textbook way to detect cycles in directed graphs. Time: O(n + m) Space: O(n)

Compute the in-degree of every vertex, push all vertices with in-degree 0 into a queue, and repeatedly pop a vertex, print/count it, and decrement the in-degree of its neighbors, pushing any neighbor whose in-degree drops to 0. If a valid topological order can only be produced for a DAG, so if the number of vertices processed this way ends up less than n, the remaining vertices must be stuck in a cycle. This avoids re-traversing the graph once per vertex and instead processes every edge exactly once overall. Time: O(n + m) Space: O(n)

1. Do a DFS from every unvisited vertex, tracking which vertices are currently 'ON THE RECURSION STACK' (still being processed) versus FULLY FINISHED. 2. A back-edge to a vertex that's STILL on the current recursion stack means a cycle. 3. A self-loop (an edge from a vertex to itself) also counts as a cycle immediately.

Time: O(n + m) - one DFS pass (across all components) visiting every vertex and edge once. Space: O(n), for the visited array, on-stack tracking array, and recursion stack.

a self-loop (an edge from a vertex to itself, which counts as a cycle), m = 0 (no cycle possible), and n at its maximum of 10^5 to confirm the DFS-based detection runs efficiently.

Be ready to contrast this precisely with UNDIRECTED cycle detection (which tracks parent, not recursion-stack membership) - directed graphs need the stronger on-stack tracking because edge DIRECTION matters for what counts as a genuine cycle.