Print all cycles in a directed graph
Filed under Amazon
Free read 3 of 3Define what constitutes a unique cycle (are cyclic shifts considered duplicate?).
The question
Given a directed graph, find and print all the unique cycles present in it.
Constraints
- Number of vertices V <= 20
- Number of edges E <= 100
- The graph is represented as an adjacency list.
Examples
- Input
- graph = {0: [1], 1: [2], 2: [0, 3], 3: [1]}
- Output
- [[0, 1, 2], [1, 2, 3]]
- Why
- Cycles found include 0->1->2->0 and 1->2->3->1.
Approach
Define what constitutes a unique cycle (are cyclic shifts considered duplicate?).
Check all possible paths using DFS to see if they end up at a previously visited node in the current path.
Use Johnson's algorithm or DFS with backtracing keeping track of the current path and a blocked set to find elementary cycles efficiently.
Self-loops, parallel edges, and acyclic graphs.
Tips
- What they are testing: Test with disconnected components, DAGs (no cycles), and complete graphs.
- Common mistake: Confusing standard DFS visited arrays with recursion-stack tracking, leading to printing duplicate rotations of the same cycle.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.