Cycle Detection

A cycle is a path that returns to where it started. In dependency problems a cycle is a deadlock (each item waits on another, so nothing can start), and in "is this a tree?" problems it is the thing that breaks the tree. The check looks different for undirected and directed graphs, and mixing the two up is the most common bug.

The idea#

A cycle means a walk can come back to a node it already visited. How you spot one depends on whether edges have a direction, so the two cases get their own rules.

Undirected: ignore the edge you came in on#

In an undirected graph every edge appears in both directions, so from a node you will always "see" the parent you came from. Pass the parent into the DFS and skip it. Any other neighbor that is already visited means there are two different routes to it, which is a cycle.

Directed: watch the current path#

In a directed graph, reaching an already visited node is not enough: two branches can lead to the same node without any cycle. What matters is whether that node is still on the current path. Track two sets:

• on_path: nodes in the chain you are exploring right now (the recursion stack).
• done: nodes whose whole subtree has been explored and proven cycle-free.

Meeting a node in on_path is a back edge, so a cycle. Meeting a node in done costs nothing: skip it.

How to spot it#

The cues split cleanly by edge type.

Template#

Here are both checks, directed first. In each one a node is fully explored at most once, so both run in $O(V + E)$.

on_path = empty set; done = empty set
dfs(node):
    if node in on_path: return cycle   # back edge
    if node in done: return no cycle   # already proven safe
    add node to on_path
    for each nei in neighbors of node:
        if dfs(nei) finds a cycle: return cycle
    remove node from on_path           # leaving the path
    add node to done                   # cache: never redo it
    return no cycle
run dfs from every node; any cycle means the graph has one

The undirected check is simpler: it needs only one seen set and the parent. Add every edge in both directions.

seen = empty set
dfs(node, parent):
    add node to seen
    for each nei in neighbors of node:
        if nei == parent: skip         # the edge you arrived on
        if nei in seen or dfs(nei, node) finds a cycle:
            return cycle
    return no cycle
run dfs(node, none) from every node not in seen

From TLE to O(V + E)#

The directed version shows why the done cache matters. A first attempt often runs the cycle check from every node with a fresh set() each time. Nothing carries over between starts, so each DFS can redo $O(V + E)$ work and the total is $O(V \cdot (V + E))$, which times out on Course Schedule.

Caching nodes that are already proven safe fixes it: a later DFS that reaches a cached node returns in $O(1)$. Each node is then explored fully at most once, each edge is followed at most once, and the total drops to $O(V + E)$.

The other easy slip is forgetting on_path.remove(node) on the way out. Without it, a node reached later through a different, cycle-free branch looks like a back edge.

Pitfalls#

These are the mistakes that most often cost a correct answer.

• Using the directed check on an undirected graph: the edge back to the parent looks like a cycle.
• Using "already visited" as the directed test: two paths meeting at a node is not a cycle.
• A fresh visited set for every start node without a cache, giving $O(V \cdot (V + E))$.
• Forgetting to remove a node from the path set when the DFS leaves it.
• Starting the DFS from one node only when the graph may have several components.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Course Schedule.

• 261. Graph Valid Tree
• 684. Redundant Connection
• 207. Course Schedule
• 802. Find Eventual Safe States

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Undirected: skip the parent; any other visited neighbor is a cycle.
• Directed: a cycle means you met a node that is still on the current path.
• Cache finished nodes, or repeated DFS starts cost $O(V \cdot (V + E))$.
• $n - 1$ edges plus connected is enough to prove a tree.
• For undirected graphs built edge by edge, Union-Find is the faster cycle check.