Longest Cycle in a Graph - Practice Coding Problems

Longest Cycle in a Graph - Problem

You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.

The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from node i, then edges[i] == -1.

Return the length of the longest cycle in the graph. If no cycle exists, return -1.

A cycle is a path that starts and ends at the same node.

Input & Output

Example 1 — Graph with Cycle

$ Input: edges = [3,3,4,2,3]

› Output: 3

💡 Note: The longest cycle is 3 → 2 → 4 → 3 with length 3. There's also a self-loop at node 1 (1 → 1) with length 1, but 3 is longer.

Example 2 — No Cycles

$ Input: edges = [2,-1,3,1]

› Output: -1

💡 Note: Following paths: 0→2→3→1→(dead end), no cycles exist in this graph, so return -1.

Example 3 — Self Loop

$ Input: edges = [1,0,0]

› Output: 2

💡 Note: There's a cycle 0 ↔ 1 with length 2. Node 2 points to node 0 but doesn't create a longer cycle.

Constraints

1 ≤ edges.length ≤ 10⁵
edges[i] == -1 or 0 ≤ edges[i] < edges.length
Each node has at most one outgoing edge

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed graph represented as edges array

DFS Traversal

Use DFS to detect cycles with timestamps

Output Result

Return length of longest cycle found

Key Takeaway

🎯 Key Insight: Since each node has at most one outgoing edge, we can use DFS with timestamps to detect cycles in a single pass with O(n) time complexity.

Asked in

G Google 15 a Amazon 12 M Microsoft 8 A Apple 6

The key insight is that since each node has at most one outgoing edge, we can use DFS with timestamps to efficiently detect cycles. The optimal approach uses a single pass with O(n) time complexity by tracking visit states and calculating cycle lengths using time differences.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Starting Points	O(n²)	O(n)	Start DFS from every node and track the longest cycle found
DFS with Global Visited Tracking	O(n)	O(n)	Use DFS with global visited set to avoid redundant exploration
Optimized DFS with Time Stamps	O(n)	O(n)	Single pass DFS using timestamps to efficiently detect cycles

Brute Force - Try All Starting Points — Algorithm Steps

For each node as starting point
Follow edges until cycle detected or dead end
Track longest cycle length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from Node 0

Follow path and check for cycles

Try Next Nodes

Repeat for all starting points

Return Maximum

Find longest cycle among all attempts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dfs(int* edges, int edgesSize, int start) {
    int* visited = (int*)calloc(edgesSize, sizeof(int));
    int* path = (int*)malloc(edgesSize * sizeof(int));
    int pathSize = 0;
    int current = start;
    
    while (current != -1 && !visited[current]) {
        visited[current] = 1;
        path[pathSize++] = current;
        current = edges[current];
    }
    
    int cycleLength = -1;
    if (current != -1 && visited[current]) {
        for (int i = 0; i < pathSize; i++) {
            if (path[i] == current) {
                cycleLength = pathSize - i;
                break;
            }
        }
    }
    
    free(visited);
    free(path);
    return cycleLength;
}

int solution(int* edges, int edgesSize) {
    int maxCycleLength = -1;
    
    for (int i = 0; i < edgesSize; i++) {
        int cycleLength = dfs(edges, edgesSize, i);
        if (cycleLength != -1) {
            if (maxCycleLength == -1 || cycleLength > maxCycleLength) {
                maxCycleLength = cycleLength;
            }
        }
    }
    
    return maxCycleLength;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int edges[10000];
    int edgesSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        edges[edgesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(edges, edgesSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we might traverse up to n edges in the worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Visited array and recursion stack depth up to n nodes

⚡ Linearithmic Space

38.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Starting Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler