Longest Cycle in a Graph

Longest Cycle in a Graph

What is this problem about?

The Longest Cycle in a Graph problem provides you with a directed graph represented by an array, where edges[i] indicates a directed edge from node i to node edges[i]. A node can have at most one outgoing edge. Your task is to find the length of the longest cycle within this graph. If no cycle exists, you must return -1.

Why is this asked in interviews?

This is a fantastic graph theory problem because the graph has a very specific constraint: each node has a maximum out-degree of 1. This special type of graph is sometimes called a "functional graph." Interviewers ask this to see if you can recognize that this constraint allows for much simpler and faster cycle-detection algorithms than standard Tarjan's or general DFS back-edge detection on dense graphs.

Algorithmic pattern used

This problem leverages the Depth-First Search (DFS) pattern combined with State Tracking. Because every node has at most one outgoing edge, a DFS path will either hit a dead end, hit a node we've already fully processed in a previous path, or hit a node currently in our DFS path. The latter case means we found a cycle! By keeping track of the "distance" from the start node during our DFS, we can instantly calculate the cycle's length when we run into a currently-visiting node.

Example explanation

Suppose edges = [3, 3, 4, 2, 3]. We maintain a visited array and track the distance in our current path.

• Start DFS at node 0. dist=0. Next is 3.
• Node 3, dist=1. Next is 2.
• Node 2, dist=2. Next is 4.
• Node 4, dist=3. Next is 3. Wait, node 3 is already in our current path! We visited it at distance 1. The current distance is 4 (since we took a step from 4). The cycle length is simply current_dist - dist_when_visited_node_3 = 4 - 1 = 3. The cycle is 3 -> 2 -> 4 -> 3.

Common mistakes candidates make

Candidates often try to use standard cycle detection algorithms meant for undirected graphs, or they struggle to keep track of the lengths. A very common error is failing to distinguish between nodes visited in the current DFS path versus nodes visited in a previous, completed DFS path. If you hit a node from a previous path, it does NOT mean you found a new cycle; it means you merged into an already-processed chain.

Interview preparation tip

When dealing with functional graphs (out-degree $\le 1$), remember that you can track cycles efficiently by passing a time_step or distance counter into your DFS. Storing a map of node -> distance_in_current_path is the cleanest way to immediately calculate the size of the cycle once a back-edge is found. Practice managing the states of nodes: Unvisited, Visiting (in current path), and Fully Processed.