• V = number of vertices, E = number of edges
• Edges are directed — following them backwards is not permitted
• The graph may be disconnected, so every vertex must be considered as a potential start
• Self-loops count as cycles
• Runs in O(V + E) time and O(V) space

A cycle is a route that leaves a vertex, follows edges forward, and returns to where it began. Detecting one sounds like it should need nothing more than a visited set — and that instinct is wrong in a way worth examining closely, because the correction is the whole lesson.

Here is the rule that works on undirected graphs: if you reach a vertex already visited, you have found a second route to it, so a cycle exists. Transplanted to directed graphs, it breaks.

Consider four vertices arranged as a diamond: A → B, A → C, B → D, C → D.

Explore from A, go to B, then to D. Three vertices are now marked visited. Back up to A and take the other branch to C. From C, follow the edge to D — and D is already visited.

Under the undirected rule you would declare a cycle. But look at the graph: every edge runs forward, from A toward D, and there is no way back to A from anywhere. This is a perfectly acyclic graph. D simply has two things pointing at it.

The reason the rule transfers badly is that in an undirected graph, having two distinct routes to a vertex genuinely is a cycle — you can go out along one and back along the other, because edges work both ways. In a directed graph you cannot come back along an edge, so two forward routes to the same place prove nothing at all.

The visited set is conflating two situations that need separating.

A vertex might be one your search is still in the middle of — you entered it, you are currently exploring things it points to, and you have not yet returned from it. In recursion terms, its stack frame is still open. Such a vertex is an ancestor of where you are now.

Or a vertex might be one your search completely finished — you entered it, explored everything reachable from it, found no cycle, and returned. It is behind you, not above you.

Now the correct rule falls out. Arriving at a vertex that is still in progress means there is a route from that vertex forward to where you now stand, and an edge from here back to it. Those two together close a loop. That is a cycle, and nothing else is.

Arriving at a finished vertex means only that something else already led there. No loop, and nothing worth re-exploring, since it was already cleared.

Encode it directly. Every vertex is in one of three states, traditionally coloured:

A vertex goes white to grey when the search enters it, and grey to black when the search leaves it. The rule is then a single line: a grey neighbour means a cycle.

def has_cycle(V, adj):
    WHITE, GREY, BLACK = 0, 1, 2
    state = [WHITE] * V

    def visit(u):
        state[u] = GREY                      # entering: now on the active path
        for v in adj[u]:
            if state[v] == GREY:
                return True                  # back-edge to an ancestor: cycle
            if state[v] == WHITE and visit(v):
                return True
        state[u] = BLACK                     # leaving: fully explored and safe
        return False

    return any(visit(u) for u in range(V) if state[u] == WHITE)

An edge leading to a grey vertex has a name worth knowing, since interviewers use it: a back-edge. A directed graph contains a cycle if and only if a depth-first search of it finds a back-edge.

Cost: each vertex is entered once, thanks to the white check, and each edge is examined once. O(V + E) time, O(V) for the state array plus up to O(V) recursion depth.

Edges 0→1, 1→2, 2→3, 3→1.

Now the diamond, A→B, A→C, B→D, C→D, to see the failure case handled correctly.

The whole difference between the two traces is whether the re-encountered vertex was grey or black.

The same question can be answered without recursion at all, using in-degree counting — Kahn's algorithm.

Count the incoming edges of every vertex. Repeatedly remove any vertex with zero incoming edges, decrementing the counts of everything it points to. If every vertex is eventually removed, the graph is acyclic. If some remain stuck with non-zero counts, those form a cycle.

The proof is the same backward-walk argument used in topological sorting: each stuck vertex has a stuck predecessor, and with finitely many vertices, following predecessors backwards must eventually repeat one.

from collections import deque

def has_cycle_kahn(V, adj):
    in_degree = [0] * V
    for u in range(V):
        for v in adj[u]:
            in_degree[v] += 1

    queue = deque(u for u in range(V) if in_degree[u] == 0)
    removed = 0
    while queue:
        u = queue.popleft()
        removed += 1
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    return removed != V          # anything left over is part of a cycle

Same O(V + E) cost. It avoids recursion entirely, which matters when V is large enough to overflow the call stack. The depth-first version has the compensating advantage that the grey vertices at the moment of detection hand you the actual cycle, which Kahn's does not.

That equivalence is worth stating outright: a directed graph is acyclic if and only if it has a topological ordering. Cycle detection and topological sorting are the same computation, differing only in what they report.

Train the reflex: in a directed graph, never ask "have I been here before?" Ask "am I still inside this vertex's exploration?" Two states are not enough; three are.