Sign in
Skip to solution
hardDSA

How do you detect a cycle in a directed graph?

999 views
01

Understand the problem

Explain cycle detection.

graphscycle
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Run DFS tracking three states (unvisited, in-progress, done). If you reach a node that's currently 'in-progress' (in the recursion stack), there's a back edge → a cycle. Alternatively, Kahn's topological sort fails to process all nodes if a cycle exists. O(V+E).

Solution ready — 2 min read

Classified // press E to declassify

04

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
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 105 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track