DSA Tracker

Visualize

Directed Graph Cycle

DFS with three colours: unseen, active (on the call stack), done

time O(V + E)space O(V)

In an undirected graph, reaching an already-visited node is enough to declare a cycle. A directed graph needs one more bit per node, because two separate paths can legitimately converge on the same target without looping — that is a cross-edge, not a cycle. The fix is to track which nodes are ACTIVE right now, meaning still open on the current DFS call path, versus DONE, meaning fully explored and safe to converge on. A cycle exists exactly when an edge points at a node that is still active — a back-edge into your own ancestry.

Details

Animated on: 7 vertices with directed edges 0->1, 1->2, 2->3, 2->6, 3->4, 4->5, 5->3 — does the graph contain a cycle?

Problem:Directed Graph CycleMedium

DFS with three colours: unseen, active (on the call stack), done

step 1 / 15

Vertices and directed edges

7 vertices and 7 directed edges. A cycle means some node can reach itself by following arrows forward — DFS finds one the moment it revisits a node that is still open on its own current path.

Pseudocode
1FUNCTION hasCycle(n, edges):
2  BUILD adjacency list next FROM edges
3  color <- ARRAY of n zeros
4  FOR u FROM 0 TO n - 1
5    IF color[u] = 0 AND dfs(u, next, color) = true
6      RETURN true
7  RETURN false
8FUNCTION dfs(u, next, color):
9  color[u] <- 1
10  FOR EACH v IN next[u]
11    IF color[v] = 1
12      RETURN true
13    IF color[v] = 0 AND dfs(v, next, color) = true
14      RETURN true
15  color[u] <- 2
16  RETURN false

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. 7 vertices and 7 directed edges. A cycle means some node can reach itself by following arrows forward — DFS finds one the moment it revisits a node that is still open on its own current path.
  2. Enter 0 and mark it active — it is now open on the call stack [0]. A back-edge INTO any of these active nodes would close a loop.
  3. 0 has an edge to 1, currently unseen.
  4. Enter 1 and mark it active — it is now open on the call stack [0, 1]. A back-edge INTO any of these active nodes would close a loop.
  5. 1 has an edge to 2, currently unseen.
  6. Enter 2 and mark it active — it is now open on the call stack [0, 1, 2]. A back-edge INTO any of these active nodes would close a loop.
  7. 2 has an edge to 3, currently unseen.
  8. Enter 3 and mark it active — it is now open on the call stack [0, 1, 2, 3]. A back-edge INTO any of these active nodes would close a loop.
  9. 3 has an edge to 4, currently unseen.
  10. Enter 4 and mark it active — it is now open on the call stack [0, 1, 2, 3, 4]. A back-edge INTO any of these active nodes would close a loop.
  11. 4 has an edge to 5, currently unseen.
  12. Enter 5 and mark it active — it is now open on the call stack [0, 1, 2, 3, 4, 5]. A back-edge INTO any of these active nodes would close a loop.
  13. 5 has an edge to 3, currently active.
  14. 3 is ACTIVE, meaning it is an ancestor of 5 on the current path — the edge 5 -> 3 closes the loop 3 -> 4 -> 5 -> 3. That is a cycle; no need to look further.
  15. The search stopped as soon as the back-edge 5 -> 3 appeared, so node 6 was never even visited — one back-edge is proof enough. RETURN true.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Directed Graph Cycle in the editorAll Graph problemsBack to roadmap