Katkat
Back

Enumerate All Simple Directed Cycles

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests graph traversal skills, specifically the ability to identify unique simple cycles in a directed graph using canonical representations to avoid duplicates.

Problem Statement

Given a directed graph represented by an adjacency list adj, where adj[u] contains a list of nodes v such that there is a directed edge from u to v, write a function that returns a list of all unique simple directed cycles in the graph.

A cycle is considered unique if it is not a cyclic shift of another cycle already found. Self-loops (a node pointing to itself) should be included as cycles of length 1.

Function Signature

def find_all_simple_cycles(adj):
    # adj: dict[int, list[int]]
    # returns: list[list[int]]

Constraints

  • The graph may contain up to 50 nodes.
  • The graph is directed and may contain cycles.
  • The nodes are labeled 0 to N-1.

Example 1

Input: adj = {0: [1], 1: [2], 2: [0, 3], 3: []} Output: [[0, 1, 2]] Explanation: The only cycle is 0 -> 1 -> 2 -> 0.

Example 2

Input: adj = {0: [0]} Output: [[0]] Explanation: A self-loop on node 0 is a cycle of length 1.

Edge Cases

  • Disconnected graph components.
  • Multiple cycles sharing nodes or edges.
  • Graphs with no cycles.

Hints

Hint 1

Consider using depth-first search (DFS) to explore paths, keeping track of the current recursion stack to detect back-edges.

Hint 2

To ensure each cycle is unique, represent each cycle by its smallest node first and sort the nodes based on a canonical rotation.

Hint 3

Store identified cycles in a set using their canonical string or tuple representation to prevent duplicate entries.

Follow-up questions

  • How would your approach change if the graph were undirected instead of directed?
  • What is the time complexity of your algorithm in the worst-case scenario (e.g., a complete directed graph)?
  • How would you optimize the cycle detection if the graph was extremely sparse?