Longest Cycle in a Graph — Solution in Python, Java & C++
Longest Cycle in a Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Longest Cycle in a Graph is a hard coding problem on depth-first search, graph and topological sort, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Depth-First Search, Graph, Topological Sort
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a directed graph of n nodes where each node has at most one outgoing edge: edges[i] is the node that i points to, or -1 if it points nowhere.
Return the length of the longest cycle, or -1 if the graph has no cycle.
Example 1
Input: edges = [3,3,4,2,3]
Output: 3
Explanation: The cycle 2 → 4 → 3 → 2 has length 3.
Example 2
Input: edges = [2,-1,3,1]
Output: -1
Example 3
Input: edges = [1,0]
Output: 2
Constraints
1 <= edges.length <= 40-1 <= edges[i] < edges.lengthedges[i] != i
Hints for Longest Cycle in a Graph
Hint 1
With one outgoing edge per node, following the arrows from any start eventually repeats a node.
Hint 2
Stamp each node with a global visit time as you walk, and stop when you reach something already stamped.
Hint 3
If that node was stamped during the current walk, the cycle length is the difference between the current clock and its stamp.
How to solve Longest Cycle in a Graph
Each node has one outgoing edge, so following arrows from any unvisited start eventually hits a visited node. Stamp nodes with a global clock; if the hit node was stamped during the current walk, the cycle length is clock - stamp.
Approach
- For each unstamped
i, recordwalkStart = clockand walk, stamping each node withclock++. - When the walk reaches a stamped node with stamp ≥
walkStart, updatebest = clock - stamp.
Why it works
A functional graph's walk is a ρ shape; a node revisited within the same walk closes the cycle, and the stamps count exactly the nodes on it. Nodes stamped by earlier walks are already resolved.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Comparing against
walkStartis what distinguishes a cycle from merging into an earlier walk's path.
Reference solution
Python
def longestCycle(edges) -> int:
n = len(edges)
visited_at = [-1] * n
best = -1
clock = 0
for i in range(n):
if visited_at[i] != -1:
continue
walk_start = clock
node = i
while node != -1 and visited_at[node] == -1:
visited_at[node] = clock
clock += 1
node = edges[node]
if node != -1 and visited_at[node] >= walk_start:
best = max(best, clock - visited_at[node])
return bestJava
public static int longestCycle(int[] edges) {
int n = edges.length;
int[] visitedAt = new int[n];
Arrays.fill(visitedAt, -1);
int best = -1, clock = 0;
for (int i = 0; i < n; i++) {
if (visitedAt[i] != -1) continue;
int walkStart = clock;
int node = i;
while (node != -1 && visitedAt[node] == -1) {
visitedAt[node] = clock++;
node = edges[node];
}
if (node != -1 && visitedAt[node] >= walkStart) {
best = Math.max(best, clock - visitedAt[node]);
}
}
return best;
}C++
int longestCycle(vector<int>& edges) {
int n = (int) edges.size();
vector<int> visitedAt(n, -1);
int best = -1, clock = 0;
for (int i = 0; i < n; i++) {
if (visitedAt[i] != -1) continue;
int walkStart = clock;
int node = i;
while (node != -1 && visitedAt[node] == -1) {
visitedAt[node] = clock++;
node = edges[node];
}
if (node != -1 && visitedAt[node] >= walkStart) {
best = max(best, clock - visitedAt[node]);
}
}
return best;
}JavaScript
var longestCycle = function(edges) {
const n = edges.length;
const visitedAt = [];
for (let i = 0; i < n; i++) visitedAt.push(-1);
let best = -1;
let clock = 0;
for (let i = 0; i < n; i++) {
if (visitedAt[i] !== -1) continue;
const walkStart = clock;
let node = i;
while (node !== -1 && visitedAt[node] === -1) {
visitedAt[node] = clock++;
node = edges[node];
}
if (node !== -1 && visitedAt[node] >= walkStart) {
const length = clock - visitedAt[node];
if (length > best) best = length;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure