• V = number of vertices, E = number of edges
• Edges are undirected — each connects its two endpoints in both directions
• The graph may be disconnected
• Assume a simple graph unless stated otherwise: no self-loops, no repeated edges
• Runs in O(V + E) time and O(V) space

A cycle here means a genuine loop: leave a vertex, come back, and never cross the same edge twice. That last clause is doing real work, and understanding why is the entire problem.

In an undirected graph, every edge works both ways. Store it as an adjacency list and the edge between A and B literally appears twice — B is in A's list, and A is in B's.

So the naive rule "if I reach a visited vertex, there is a cycle" fires instantly and always. Start at A, mark it, step to B, mark it, and then look at B's neighbours: A is there, and A is visited. Cycle reported — on a graph with a single edge.

That is nonsense, and the definition already told us why: walking A to B to A reuses the same edge. It is not a loop, it is a retraced step. So the algorithm needs to distinguish the edge you just arrived on from any other edge leading somewhere you have been.

When the search moves from A to B, pass along the fact that it came from A. Then, while examining B's neighbours, skip A once — that is the edge just used.

Now consider what it means to find any other visited neighbour. Suppose the search is at vertex X and sees a visited neighbour Y that is not its parent. Y being visited means the search reached it earlier by some route, and that route did not come through the edge X–Y, since that edge is being examined for the first time now. So there are two distinct routes between X and Y: the earlier one, and the direct edge. Two distinct routes joined together form a loop that uses no edge twice.

That is a complete argument, and it works in both directions — if a cycle exists, the search must eventually enter it and come around to a vertex already visited by a different edge. So this test is exact, not approximate.

def has_cycle(V, adj):
    visited = [False] * V

    def visit(u, parent):
        visited[u] = True
        for v in adj[u]:
            if v == parent:
                continue                      # the edge we just crossed
            if visited[v]:
                return True                   # a second route to v: cycle
            if visit(v, u):
                return True
        return False

    for u in range(V):
        if not visited[u] and visit(u, -1):   # -1: the root has no parent
            return True
    return False

Cost: every vertex is entered once and every edge examined twice, once from each end, so O(V + E) time with O(V) for the visited array and the recursion stack.

It is worth setting the two side by side, because the rules look superficially similar and are not.

In a directed graph, reaching a visited vertex proves nothing — several forward routes may lead to the same place with no loop involved. There, a cycle requires reaching a vertex that is still in progress on the current path, which needs three states.

In an undirected graph, reaching a visited vertex that is not your parent is a cycle, and two states suffice. The reason for the difference is that undirected edges are traversable both ways, so two routes to a vertex can always be joined into a loop by walking one of them backwards. In a directed graph you cannot walk backwards, so two routes stay two routes.

Same word, different structure, different algorithm. Confusing them is a classic interview error, so being able to state the distinction is worth as much as the code.

Edges 0-1, 1-2, 2-3, 3-1.

Adjacency: node 0 has [1]; node 1 has [0, 2, 3]; node 2 has [1, 3]; node 3 has [2, 1].

The detected cycle is 1-2-3-1, using the three edges 1-2, 2-3 and 3-1, none repeated.

Now the chain 0-1, 1-2, 2-3, which has no cycle. The search walks 0 → 1 → 2 → 3, and at each step the only visited neighbour is the parent, which is skipped. Node 3 has just the one neighbour 2, its parent, so the recursion unwinds returning false all the way. The outer loop finds every vertex visited and returns false.

Two facts are worth carrying away.

The first is a structural one. A tree — connected and acyclic — on V vertices has exactly V-1 edges. Fewer than V-1 edges and the graph cannot be connected; more than V-1 and it cannot be acyclic. So on a graph promised to be connected, counting edges answers the question outright: E ≥ V means a cycle exists. That will not tell you where, and it fails on disconnected graphs, where a component can carry a cycle while the total edge count stays low. But it is the reasoning behind Redundant Connection, where exactly V edges on V vertices guarantee exactly one cycle.

The second is a different algorithm entirely. When the input is a list of edges rather than an adjacency structure, union-find is more natural than traversal. Process edges one at a time, maintaining which vertices are currently in the same connected group. For an edge joining u and v, ask whether they are already in the same group — if so, they were already connected by some earlier route, and this edge closes a loop.

def has_cycle_dsu(V, edges):
    parent = list(range(V))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]     # path halving: flattens as it walks
            x = parent[x]
        return x

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return True                       # already connected: this edge closes a cycle
        parent[ru] = rv
    return False

It costs O(E · α(V)), where α is the inverse Ackermann function — under 5 for any input that fits in memory, so effectively constant per edge. Its real advantage is that it works incrementally: edges can arrive over time and each query is answered immediately, where a traversal would have to rerun from scratch. That property is what Redundant Connection and Number of Provinces are built on.

Train the reflex: in an undirected graph, a cycle is just a second way to reach somewhere you have already been. Whether you detect it by skipping the edge you came in on, or by noticing that two vertices were already connected before you joined them, is a matter of what form the input arrives in.