What is the brute force approach and complexity for Detect Cycle in a Directed Graph?

For each node s, search along the arrows; if the search reaches s again, there is a cycle with time complexity O(V · (V + E)) and space complexity O(V + E).

What is the optimal approach and complexity for Detect Cycle in a Directed Graph?

One DFS over the whole graph; an arrow into a grey node (on the current path) closes a cycle with optimal time complexity O(V + E) and space complexity O(V).

How do you identify the pattern for Detect Cycle in a Directed Graph?

Look for key signals in the prompt: "directed graph" indicates Arrows have a direction. A cycle has to follow the arrows forward, so the direction matters.; "detect a cycle" indicates A yes or no question: is there a loop? The DFS colours tell us when a loop closes.; "nodes 0 to V − 1 and an edge list" indicates Build an adjacency list first, then start a search from every node that is not yet finished..

Detect Cycle in a Directed Graph

Medium·GeeksforGeeks Pro OnlyBasic Reinforcement

GeeksforGeeks

Problem Statement

You are given a directed graph with V nodes, numbered from 0 to V − 1, and a list of directed edges. Each edge [u, v] is an arrow from u to v.

Return true if the graph has a cycle. A cycle is a walk that follows the arrows and comes back to the node where it started. Return false if there is no such walk.

Input

V, the number of nodes, and edges, a list of pairs [u, v] where u → v is an arrow.

Output

true if the directed graph contains a cycle, otherwise false.

Example 1

Input: V = 4, edges = [[0, 1], [1, 2], [2, 3]]

Output: false

A straight chain 0 → 1 → 2 → 3. Following the arrows always moves forward, so no walk comes back.

Example 2

Input: V = 4, edges = [[0, 1], [1, 2], [2, 0], [2, 3]]

Output: true

The walk 0 → 1 → 2 → 0 returns to node 0, so there is a cycle. The arrow 2 → 3 is not part of it.

Example 3

Input: V = 2, edges = [[0, 1], [1, 0]]

Output: true

Two nodes with arrows both ways: 0 → 1 → 0 is a cycle.

Constraints

• Nodes are numbered from 0 to V − 1.
• Every edge is directed: [u, v] is an arrow from u to v only.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“directed graph”

→ Arrows have a direction. A cycle has to follow the arrows forward, so the direction matters.

“detect a cycle”

→ A yes or no question: is there a loop? The DFS colours tell us when a loop closes.

“nodes 0 to V − 1 and an edge list”

→ Build an adjacency list first, then start a search from every node that is not yet finished.

Approach Complexity Ladder

Brute Force — walk from every node and see if it comes backO(V · (V + E))O(V + E)

For each node s, search along the arrows; if the search reaches s again, there is a cycle

Optimal — three-colour DFS: a grey neighbour means a cycleO(V + E)O(V)

One DFS over the whole graph; an arrow into a grey node (on the current path) closes a cycle

Brute Force Intuition

A directed graph has a cycle exactly when some node can reach itself by following arrows. So for each node s, run a search from s along the arrows. If the search reaches s again, there is a cycle.

Recognition rule for this sub-pattern:

If Kahn processes fewer than n nodes (or DFS finds a "visiting" node again), there is a cycle.

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Course Schedule Find Eventual Safe States