Skip to content
Hello Python

Detect a Directed Cycle

Practice ExerciseIntermediateMediumGraphCycle Detection

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement has_directed_cycle(node_count, edges). Return True exactly when the directed graph contains a cycle.

Starter code

def has_directed_cycle(node_count, edges):
    pass
Test cases

cycle

{
  "args": [
    3,
    [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        2,
        0
      ]
    ]
  ]
}

Expected: true

dag

{
  "args": [
    4,
    [
      [
        0,
        1
      ],
      [
        0,
        2
      ],
      [
        1,
        3
      ],
      [
        2,
        3
      ]
    ]
  ]
}

Expected: false

Wizard outline
  1. Step 1: Represent an unvisited graph

    Build adjacency lists and return false when no edge can form a cycle. Cycle detection needs explicit outgoing edges and a state per node.

  2. Step 2: Detect a back edge from one start

    Mark the active recursion path and recognize a neighbor already on it. A directed cycle is observable when DFS reaches an active node.

  3. Step 3: Start DFS in every component

    Detect cycles that are disconnected from node 0. The input graph does not guarantee one connected component.

Footguns and prerequisites
  • Treating any visited edge as a cycle confuses cross edges with back edges.
  • Starting from node zero alone misses disconnected cycles.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Run DFS with unseen, active, and complete colors from every component.

Why it works: 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.

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)