{"id":255,"date":"2025-06-03T15:54:31","date_gmt":"2025-06-03T10:24:31","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=255"},"modified":"2025-06-03T15:54:32","modified_gmt":"2025-06-03T10:24:32","slug":"detect-cycle-in-a-directed-graph","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/detect-cycle-in-a-directed-graph\/","title":{"rendered":"Detect Cycle in a Directed Graph"},"content":{"rendered":"\n

See how to solve “detect cycle in a directed graph” using depth-first search and two helper arrays. Simple idea, commented Python code, dry run, and Big-O analysis.<\/p>\n\n\n\n

What does the problem ask?<\/h2>\n\n\n\n

You are given a directed graph with V<\/code> vertices (0 \u2026 V-1<\/code>) and a list of edges.
Return True<\/code><\/strong> if the graph contains at least one directed cycle<\/strong>; otherwise return False<\/code><\/strong>. geeksforgeeks.org<\/a><\/p>\n\n\n\n

\n\n\n\n

Examples<\/h2>\n\n\n\n
V<\/code><\/th>edges<\/code><\/th>Result<\/th>Why<\/th><\/tr><\/thead>
4<\/code><\/td>[(0,1),(1,2),(2,0),(2,3)]<\/code><\/td>True<\/strong><\/td>0 \u2192 1 \u2192 2 \u2192 0 forms a cycle<\/td><\/tr>
3<\/code><\/td>[(0,1),(1,2)]<\/code><\/td>False<\/strong><\/td>No path returns to an earlier node<\/td><\/tr>
1<\/code><\/td>[(0,0)]<\/code><\/td>True<\/strong><\/td>Self-loop is a cycle<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n

Intuition & Approach<\/h2>\n\n\n\n

Key idea<\/h3>\n\n\n\n

While doing DFS, a back edge<\/strong> (an edge to a node already in the current recursion path) means a cycle.<\/p>\n\n\n\n

How we detect that<\/h3>\n\n\n\n

We keep two arrays:<\/p>\n\n\n\n