hardDSA

How do you detect a cycle in a directed graph?

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

**Intuition.** In a directed graph, a cycle is a **back edge** — an edge that points to a node still being explored on the current DFS path. Track three states per node: **unvisited**, **in-progress** (on the recursion stack), and **done**. Reaching an in-progress node means you've looped back to it. edge to a gray (in-progress) node = cycle <path d="M280,120 Q200,150 90,90" fill="none" stroke="#ef4444" str

999 views

Understand the problem

Explain cycle detection.

graphscycle

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

DFS with 3 colors

Run Playground

def has_cycle(graph, n):
    # 0 = unvisited, 1 = in-progress, 2 = done
    state = [0] * n

    def dfs(u):
        state[u] = 1
        for v in graph[u]:
            if state[v] == 1:        # back edge -> cycle
                return True
            if state[v] == 0 and dfs(v):
                return True
        state[u] = 2
        return False

    return any(state[i] == 0 and dfs(i) for i in range(n))


# --- demo ---
print(has_cycle([[1], [2], [0]], 3))   # True  (0->1->2->0)
print(has_cycle([[1], [2], []], 3))    # False

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you merge k sorted lists?

How do you find the minimum window substring?