cf.completefrontend
GRAPHS · CORE

Cycle detection

Find out whether a graph has a loop, a path that leads back to where it started, using DFS with three colors.

Time O(n + e)Space O(n + e)7 practice problemsStep-through picture

The idea

A cycle is a path that starts at a node and comes back to it, like a → b → c → a. Cycles matter: a module that imports itself through other modules, a redirect that sends you in circles, or a task that waits for itself can never finish.

For a directed graph, the classic method is DFS with three colors. White means "not visited yet". Gray means "on the current DFS path", still being explored. Black means "fully explored, no cycle through it". If DFS ever follows an edge to a gray node, it has walked back onto its own path, which is a cycle.

Undirected graphs work differently, because every edge goes both ways. There, an edge back to any visited node other than the one you just came from means a cycle. Union-find is another easy way: if an edge connects two nodes that are already in the same group, that edge closes a cycle.

An everyday example

Leaving breadcrumbs on a hike

On a hike through crossing trails, you drop blue breadcrumbs on the trail you're on right now. When you turn back from a dead end, you swap your blue crumbs for gray stones that mean "explored, nothing here". If you ever find blue crumbs in front of you, you've walked in a circle. Gray stones are fine: that trail was already explored and it doesn't lead back to you.

How the example maps to the code
In the exampleIn the code
An unexplored trailcolor[node] === "white"
Blue crumbs on your current trailcolor[node] = "gray"
Gray stones on fully explored trailscolor[node] = "black"
Finding your own blue crumbs aheadcolor[next] === "gray": a cycle

From the slow way to cycle detection

  1. The obvious check: for each node, run a search and see whether it can come back to itself. That is n searches of n + e each. On a module graph with 10,000 files and 50,000 imports, that is about 600 million steps.
  2. But one DFS already walks along paths. If the graph has a loop, DFS will at some point stand on a node and see an edge back to a node on the path it is walking right now. That edge, plus the path, is the loop. So one walk can find it.
  3. A plain visited flag isn't enough for that. A visited node may be on the current path, which means a loop, or it may have been finished on some earlier branch, which doesn't. Two paths that meet at the same node are not a loop. So nodes need two kinds of visited: gray for "on the current path" and black for "finished".
  4. Color a node gray when its call starts and black when it returns. An edge to a gray node is a loop. An edge to a black node is safe. Start from every white node so no part of the graph is skipped. That is cycle detection with three colors.

How it works

  1. Build graph from the edges and color every node "white".
  2. For each white node, start visit(node).
  3. In visit, color the node "gray": it is now on the current path.
  4. For each neighbor: if it is gray, you found a cycle, so return true. If it is white, visit it, and pass up true if that finds a cycle.
  5. After all neighbors, color the node "black" and return false: no cycle goes through it.
  6. If no visit finds a gray neighbor, the graph has no cycle.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function hasCycle(n, edges) {
  2. const graph = Array.from({ length: n }, () => []);
  3. for (const [from, to] of edges) graph[from].push(to);
  4. const color = new Array(n).fill("white");
  5. function visit(node) {
  6. color[node] = "gray";
  7. for (const next of graph[node]) {
  8. if (color[next] === "gray") return true;
  9. if (color[next] === "white" && visit(next)) return true;
  10. }
  11. color[node] = "black";
  12. return false;
  13. }
  14. for (let node = 0; node < n; node++) {
  15. if (color[node] === "white" && visit(node)) return true;
  16. }
  17. return false;
  18. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

Every node is colored at most twice and every edge is checked once. The graph holds the edges; the colors and the call stack hold up to n entries.

  • Best caseO(n + e)

    Building graph reads every edge. After that, the search can stop almost at once, for example on a self-loop at node 0.

  • Average caseO(n + e)

    The search stops at the first cycle it meets, after exploring part of the graph.

  • Worst caseO(n + e)

    There is no cycle, so every node turns gray and black and every edge is checked once.

Common mistakes

  • Using only visited and not-visited. In a directed graph, two paths that meet at the same node look like a cycle when they aren't.
  • Using the directed method on an undirected graph. Every edge leads straight back to its parent, so everything looks like a cycle.
  • Forgetting to turn nodes black after exploring them, so later searches see stale gray nodes.
  • Only starting from node 0, missing cycles in other parts of the graph.

When to use it

Look for these clues in a problem:

  • The question asks whether something can loop forever, depend on itself, or be impossible to order.
  • The input is a set of dependencies, imports, or redirects that should never go in a circle.
  • You need to know if a group of edges forms a tree (connected with no cycles).
  • A topological sort is mentioned, because it only exists when there is no cycle.

Check yourself

Answer each one in your head first, then open it.

Why can't a single visited flag detect cycles in a directed graph?

It can't tell "on my current path" from "finished on another branch". In a diamond, the bottom node is reached twice without any loop, and a flag alone would call that a cycle.

What do the gray nodes represent at any moment?

The current chain of visit calls, from the node the outer loop started at down to the node being explored now.

In the trace, why didn't the edge 0 → 2 count as a cycle?

2 was black by then: it had finished, and everything it can reach is finished. It can't lead back to 0.

Why does the outer loop start from every white node instead of just node 0?

A cycle can sit in a part of the graph that node 0 can't reach. In the trace, the loop 3 → 4 → 5 → 3 was only found by the second start.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

At every moment, the gray nodes are exactly the calls on the call stack, in order, and each one has an edge to the next. So when an edge goes from the current node to a gray node, it goes back to an earlier point on that chain, and the chain plus the edge is a real cycle. A true answer is never wrong.

A black node can never lead back to a gray one. When a node turns black, every edge out of it went to a black node, since a gray one would have returned true and a white one was visited and turned black. So everything reachable from a black node is black, and stepping onto it can't close a loop through the current path.

If a cycle exists, it is found. Let x be the first node of the cycle to turn gray. At that moment every other node on the cycle is white and reachable from x, so all of them are visited before x turns black. The node just before x on the cycle then follows its edge to x while x is still gray. The search ends because each node turns gray once and each edge is checked once.

Going deeper

3 more ideas

Why gray means a cycle and black doesn't

The gray nodes are exactly the nodes on the current path from where this DFS started to the current node. An edge to a gray node closes a loop along that path. A black node was fully explored earlier and none of its paths reached a gray node at that time, so stepping onto it can't lead back to the current path.

Undirected graphs

In an undirected graph, the edge you just came along leads straight back to your gray parent, which is not a real cycle. So pass the parent into visit and ignore it once. Any other visited neighbor means a cycle. With union-find, process the edges one by one: if find(a) === find(b) before joining them, that edge closes a cycle.

Cost

Each node changes color at most twice and each edge is followed once, so it runs in O(n + e) time with O(n) extra memory for the colors and the call stack.

Work it by hand

Every step in a table, with why

A directed graph in two pieces. The first piece has two paths that meet; the second piece has a loop.

n = 6, edges = [[0, 1], [0, 2], [1, 2], [3, 4], [4, 5], [5, 3]]

StepStepnodecolor (w/g/b)Why
1visit(0)0g w w w w w0 turns gray: it is the start of the current path. w, g, and b stand for white, gray, and black.
2Edge 0 → 1, visit(1)1g g w w w w1 is white, so the path grows to 0 → 1.
3Edge 1 → 2, visit(2)2g g g w w wThe path is now 0 → 1 → 2.
42 turns black2g g b w w w2 has no outgoing edges, so nothing below it loops. It leaves the path.
51 turns black1g b b w w w1 has no more edges either.
6Edge 0 → 20g b b w w w2 is black, not gray. It was reached by another path and finished; it can't lead back to 0, so this is not a loop.
70 turns black0b b b w w wThe first piece has no cycle.
8Outer loop: visit(3)3b b b g w w1 and 2 are black, so the outer loop skips them. 3 is the next white node.
9visit(4), then visit(5)5b b b g g gThe path is now 3 → 4 → 5, all gray.
10Edge 5 → 35b b b g g g3 is gray: it is on the current path. The edge closes the loop 3 → 4 → 5 → 3, so visit returns true all the way up.

It returns true. The first piece shows the case that fools a visited flag: 2 is reached twice, but it was black the second time. The loop is only found when the outer loop starts a search in the second piece.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Cycle detectionO(n + e)O(n + e)Directed graphs, when you want a yes or no, or the cycle itself, from one walk.
Kahn's algorithmO(n + e)O(n + e)Directed graphs that may be very deep, or when you need an order whenever there is no cycle.
Union-findO(e · α(n))O(n)Undirected graphs, especially when edges arrive one at a time and you need the first edge that closes a loop.
A separate search from every nodeO(n² + n · e)O(n)Almost never. It only makes sense for tiny graphs, or if you need every node that lies on some cycle.

Extra memory: O(n + e): the adjacency list holds every edge, color holds n strings, and the call stack can be n calls deep.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Cycle detection and the other approaches, on a scale where each line up is 10 times more steps.
  • Cycle detection, Kahn's algorithm O(n + e)
  • Union-find O(e · α(n))
  • A separate search from every node O(n² + n · e)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Cycle detection202,0002 million
Kahn's algorithm202,0002 million
Union-find101,0001 million
A separate search from every node2002 million2 trillion

Inputs that need care

5 tricky inputs
A self-loop: [[2, 2]]
visit(2) turns 2 gray, then its edge leads to 2 itself, which is gray. It returns true: a node waiting on itself is a cycle.
No edges at all
Every node turns gray and black at once, and the answer is false.
Two paths that meet, as in the trace's first piece
The second arrival finds a black node and does nothing. The answer for that piece is false.
An undirected edge stored both ways: [[0, 1], [1, 0]]
This code reports true, because 1 sees its gray parent 0. For undirected graphs, skip the parent, or use union-find instead.
A chain of 200,000 nodes
The recursion is 200,000 calls deep and throws "Maximum call stack size exceeded". Use Kahn's algorithm: the graph has a cycle exactly when its order comes out shorter than n.

Variations and follow-ups

Twists interviewers add

Undirected graphs

Pass the parent into visit and ignore the edge back to it once. Any other visited neighbor means a cycle. If the graph can have two parallel edges between the same nodes, skip by edge index instead, since two parallel edges do form a cycle.

Union-find for undirected edges

Read edges one at a time. If find(a) === find(b) before joining them, a and b were already connected, so this edge closes a cycle. This also says which edge closed it.

Kahn's algorithm

Run Kahn's topological sort. If order ends with fewer than n nodes, there is a cycle. It needs no recursion, so it handles very deep graphs.

Printing the cycle

Keep a parent array set when each node is visited. When an edge from node reaches a gray next, walk parent back from node until you reach next. Those nodes, reversed, form the cycle.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "circular dependency", "deadlock", "can all tasks be finished?", or "does this form a tree?".
  • Ask first whether the graph is directed. The three-color method is for directed graphs; undirected graphs need the parent rule or union-find.
  • Test by hand on a diamond, 0 → 1, 0 → 2, 1 → 3, 2 → 3. It has no cycle, and it is exactly the input where a plain visited flag wrongly says yes.
  • Expect "can you print the cycle?": keep parent pointers and walk back from the edge that found the gray node.

Where frontend code uses it

The same idea in real UI code
  • Bundlers and linters warn about circular imports, where a.js imports b.js and b.js imports a.js, which can leave values undefined when a module first runs.
  • Routing and CDN configs check redirect rules for loops before deploying, because browsers stop after too many redirects.
  • JSON.stringify throws "Converting circular structure to JSON" when an object refers back to itself, and deep clone helpers keep a set of objects on the current path to handle that case.

Related algorithms