Workspace

Problem workspace

3 day streakD

Directed Cycle Detection

MediumGraphsOrdering

The challenge

Determine whether a directed graph contains a cycle, using DFS states to distinguish an active ancestor from a vertex whose search has already finished.

This three-state test is for directed graphs. In undirected graphs, skip the parent edge or use DSU.

Example

The DAG has no cycle. Add D → B and the active path B → C → D returns to B.

Use the walkthrough below to inspect the input and each state change.

See Directed cycles, step by step

Follow the edges. Watch the state change.

Directed · 6 vertices · 6 edgesA = 0, B = 1, …
DAGDirected graph with 6 vertices. Track three states per vertex. Unseen vertices have not been entered; active vertices are on the recursion path; done vertices have finished. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisited
DFS state
ABCDEF
unseenunseenunseenunseenunseenunseen
Step 01 / 14

Track three states per vertex.

Unseen vertices have not been entered; active vertices are on the recursion path; done vertices have finished.

state = [0] * V

Active DFS path · top last

Empty
View input edges

A → B · A → F · B → C · F → C · C → D · D → E

Put it into code

An edge to an active vertex closes a directed cycle; an edge to a finished vertex does not.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

def has_directed_cycle(adj):
    state = [0] * len(adj)  # 0: unseen, 1: active, 2: done

    def visit(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                return True  # Back edge into the active path.
            if state[v] == 0 and visit(v):
                return True
        state[u] = 2
        return False

    for u in range(len(adj)):
        if state[u] == 0 and visit(u):
            return True
    return False

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap