How do you detect a cycle in a directed graph? | Interview Question

Q: How do you detect a cycle in a directed graph?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Picture an office where nobody may start work until someone else hands them something. Ana waits for Ben's report. Ben waits for Chen's numbers. Chen waits for... Ana's sign-off. Everyone is busy *waiting*, nobody is working, and nothing will ever happen. Computers call this a **deadlock**, and the classic way to detect one is exactly this: draw an arrow from each waiting party to the party it waits for (a *wait-for graph*), and look for a loop. The same loop check appears everywhere: a spreadsheet

The problem

Question presented to candidate: "Given a directed graph with n nodes and a list of edges, tell me whether it contains a cycle. If you can, return one cycle as a list of nodes. Please code it in Python."

What a strong answer should cover:

Why a single "visited" flag gives false positives in a directed graph (a diamond is not a cycle).
Three-colour DFS: WHITE/GRAY/BLACK, a cycle exactly when an edge reaches a GRAY node (a back edge), and why BLACK nodes are safe.
Restarting DFS from every unvisited node, self-loops, and recovering the cycle from the current path.
O(V + E) time and O(V) extra space, with Kahn's algorithm as the non-recursive alternative.
Python specifics: a nested visit function closing over a color list, any(...) over start nodes, the 1000-frame default recursion limit, and returning the cycle with list slicing.

Clarifying questions expected:

"Do you need just true/false, or the cycle itself?"
"Can there be self-loops, and is the graph connected?"

Code / implementation expected: Yes — a three-colour DFS hasCycle (ideally returning the cycle) in Python.

graphs
cycle

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Picture an office where nobody may start work until someone else hands them something. Ana waits for Ben's report. Ben waits for Chen's numbers. Chen waits for... Ana's sign-off. Everyone is busy waiting, nobody is working, and nothing will ever happen. Computers call this a deadlock, and the classic way to detect one is exactly this: draw an arrow from each waiting party to the party it waits f

The solution is hidden so you can try first

12 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonThree-colour DFS that labels every edge and returns the cycle

Practice

PythonWhy one visited flag is wrong: naive vs three colours vs Kahn

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.