Longest Cycle in a Graph
Asked at Anduril
Problem
Longest Cycle in a Graph gives you a directed graph where every node has at most one outgoing edge (edges[i], or -1), and asks for the length of the longest cycle, or -1 if none exists. Because each node has a single successor, you can walk paths directly and detect cycles with visit timestamps.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Hard | View all Anduril questions → |
How to Think About It
With at most one outgoing edge per node, following edges from any node traces a single path that either stops at -1 or eventually loops.
Key insight: walk from each unvisited node, stamping every node with a global increasing time. Remember the time at which this walk started.
If the walk reaches a node stamped during the current walk (its stamp is at least the start time), you found a cycle of length currentTime - stamp[node].
If it reaches a node stamped by an earlier walk, stop — that region has already been fully explored.
Each node is stamped once, so the total work is O(n).
Optimal Approach
Step 1: stamp = [0] * n, time = 1, best = -1.
Step 2: For each node s with stamp[s] == 0:
start = time, u = s.
While u != -1 and stamp[u] == 0: stamp[u] = time, time += 1, u = edges[u].
If u != -1 and stamp[u] >= start: best = max(best, time - stamp[u]).
Step 3: Return best.
Time: O(n). Space: O(n).
What Trips People Up in Real Interviews
Using a general cycle-detection DFS with recursion — correct but heavier, and it can overflow the stack on long chains.
Counting a cycle when the walk runs into a node visited by a previous walk. Only nodes stamped in the current walk form a new cycle.
Resetting visited marks between starting nodes, which makes the algorithm quadratic.
Forgetting nodes with edges[i] == -1.
Solution Code
def longestCycle(edges):
n = len(edges)
stamp = [0] * n
time = 1
best = -1
for s in range(n):
if stamp[s]:
continue
start = time
u = s
while u != -1 and stamp[u] == 0:
stamp[u] = time
time += 1
u = edges[u]
if u != -1 and stamp[u] >= start:
best = max(best, time - stamp[u])
return bestFrequently Asked Questions
What is the Longest Cycle in a Graph problem?
Longest Cycle in a Graph gives you a directed graph where every node has at most one outgoing edge (`edges[i]`, or -1), and asks for the length of the longest cycle, or -1 if none exists. Because each node has a single successor, you can walk paths directly and detect cycles with visit timestamps.
How do you solve Longest Cycle in a Graph?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Cycle in a Graph?
Longest Cycle in a Graph is asked at Anduril. It is a hard difficulty problem.
What are common mistakes on Longest Cycle in a Graph?
- Using a general cycle-detection DFS with recursion — correct but heavier, and it can overflow the stack on long chains.
- Counting a cycle when the walk runs into a node visited by a previous walk. Only nodes stamped in the current walk form a new cycle.
- Resetting visited marks between starting nodes, which makes the algorithm quadratic.
- Forgetting nodes with `edges[i] == -1`.