Skip to content
Hello Python
Algorithm1 Practice2 Interview

Cycle Detection

Detect repeated reachability state using DFS colors, indegrees, union-find, or fast-slow pointers. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Cycle Detection when the prompt's constraints and required operations match this shape: Detect repeated reachability state using DFS colors, indegrees, union-find, or fast-slow pointers.

Pybit demonstrates Cycle Detection in a professional Python interview workspace.
On this page · Match Detection to Graph Direction

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Cycle Detection Code Labs

Match Detection to Graph Direction

Cycle evidence differs by graph model. A directed edge to an active ancestor is a cycle; an undirected edge back to the immediate parent is expected and must be excluded.

Track Active DFS Paths

Use three colors: unseen, active, and finished. Only an edge to active state is a directed back edge; an edge to a finished node may simply join a previously completed path.

Trace DFS Color Changes

Reference
def color_trace(adjacency,start):
    colors=[0]*len(adjacency);events=[]
    def visit(node):
        colors[node]=1;events.append([node,1])
        for neighbor in adjacency[node]:
            if colors[neighbor]==0:visit(neighbor)
        colors[node]=2;events.append([node,2])
    if start!=-1:visit(start)
    return events
Practice

Implement color_trace(adjacency,start). Return [node,color] events where color 1 enters the active path and 2 finishes.

Public tests

  • Separate active from finished nodes

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Parent Edges in Undirected Graphs

For undirected DFS, carry the parent and report a visited neighbor only when it is not that parent. Parallel-edge policy may require edge IDs rather than just parent nodes.

Detect a Directed Cycle

Reference
def has_directed_cycle(adjacency):
    colors=[0]*len(adjacency)
    def visit(node):
        colors[node]=1
        for neighbor in adjacency[node]:
            if colors[neighbor]==1:return True
            if colors[neighbor]==0 and visit(neighbor):return True
        colors[node]=2;return False
    return any(colors[node]==0 and visit(node) for node in range(len(adjacency)))
Practice

Implement has_directed_cycle(adjacency). Return whether any DFS reaches an active-path node.

Public tests

  • Detect only active-path back edges

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Coloring Indegrees or Union Find

Use DFS coloring to locate directed cycle structure, Kahn’s processed count to test DAG feasibility, and union-find for cycles created by undirected edge additions. Each standard method is O(V + E).

Explain It in an Interview

Say: “Visited means seen sometime; active means on the current recursion path. Only active-path edges close a directed cycle.” Identify the graph direction, disconnected components, self-loops, and the precise evidence your method returns.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Cycle Detection proof does not depend on a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Cycle Detection complete workflowO(V + E)O(V + E)Run DFS with unseen, active, and complete colors from every component.

Space

O(V + E) for the focused Detect a Directed Cycle implementation.

Assumptions

  • An edge to an active node returns to an ancestor and is a cycle. Completed nodes cannot create a new back edge for the current path. Searching every unseen node covers all components.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Cycle Detection invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Each visited marker or color has one direction-aware meaning.
  3. A detected conflict corresponds to a real edge or repeated path state in the input.
  4. Distinguish unseen, active, and completed nodes. Preserve this claim after every transition.
  5. Search every disconnected component. Preserve this claim after every transition.

When To Use Or Avoid Cycle Detection

Use It When

  • Use Cycle Detection when this precondition is stated or can be proved: The representation and direction determine whether colors, indegrees, union-find, or fast-slow pointers are valid.
  • Use it when this maintained state removes repeated work: Each visited marker or color has one direction-aware meaning.

Choose Another Tool When

  • Avoid Cycle Detection when this precondition is absent: The representation and direction determine whether colors, indegrees, union-find, or fast-slow pointers are valid.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The representation and direction determine whether colors, indegrees, union-find, or fast-slow pointers are valid.

Avoid

def has_directed_cycle(node_count, edges):
    pass

Use instead

def has_directed_cycle(node_count, edges):
    graph = [[] for _ in range(node_count)]
    for source, target in edges:
        graph[source].append(target)
    color = [0] * node_count
    def visit(node):
        if color[node] == 1:
            return True
        if color[node] == 2:
            return False
        color[node] = 1
        for neighbor in graph[node]:
            if visit(neighbor):
                return True
        color[node] = 2
        return False
    return any(visit(node) for node in range(node_count) if color[node] == 0)

Where you will hit this: Detect a Directed Cycle(opens in a new tab)

Breaking the state transition

Searches only the component containing node zero.

Prevent it: Preserve this proof obligation: The tracked state distinguishes an active revisit or incompatible edge from a harmless completed revisit.

Avoid

def has_directed_cycle(n,edges):
    return False

Use instead

def has_directed_cycle(node_count, edges):
    graph = [[] for _ in range(node_count)]
    for source, target in edges:
        graph[source].append(target)
    color = [0] * node_count
    def visit(node):
        if color[node] == 1:
            return True
        if color[node] == 2:
            return False
        color[node] = 1
        for neighbor in graph[node]:
            if visit(neighbor):
                return True
        color[node] = 2
        return False
    return any(visit(node) for node in range(node_count) if color[node] == 0)

Where you will hit this: Detect a Directed Cycle(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(V + E).

Avoid

def has_directed_cycle(n,edges):
    return False

Use instead

def has_directed_cycle(node_count, edges):
    graph = [[] for _ in range(node_count)]
    for source, target in edges:
        graph[source].append(target)
    color = [0] * node_count
    def visit(node):
        if color[node] == 1:
            return True
        if color[node] == 2:
            return False
        color[node] = 1
        for neighbor in graph[node]:
            if visit(neighbor):
                return True
        color[node] = 2
        return False
    return any(visit(node) for node in range(node_count) if color[node] == 0)

Where you will hit this: Find the Duplicate Number(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.