Length of Longest Cycle in a Directed Graph

The Longest Cycle problem is a graph-based problem where each node has at most one outgoing edge. This special structure makes the graph behave like a functional graph, allowing us to use optimized traversal techniques for cycle detection.

Problem Summary

You are given a directed graph with the following properties:

Nodes are labeled from 0 to V-1
Each node has at most one outgoing edge
The graph may contain cycles

Your task is to:

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

Key Observation

Since each node has only one outgoing edge, the graph behaves like:

A combination of chains and cycles
A structure similar to a functional graph

Example:

0 → 5 → 6 → 3 → 1 → 0

This forms a cycle.

Core Idea

We use a DFS-like traversal combined with visitation tracking.

We maintain:

visited[] → marks nodes that are already processed
time[] → stores when a node was visited in the current traversal path

How Cycle Detection Works

While traversing the graph:

When we visit a node, we assign it a timestamp
If we reach a node that is already visited in the current path, a cycle is detected

Cycle Length is calculated as:

currentStep - time[node]

Approach

Traverse each node from 0 to V-1
If the node is not visited, start traversal
Track nodes in the current path using timestamps
If a cycle is found, compute its length
Keep track of the maximum cycle length

Java Code (Optimized Solution)

import java.util.*;

class Solution {
    public int longestCycle(int V, int[][] edges) {
        int[] out = new int[V];
        Arrays.fill(out, -1);
        
        // Build graph (each node has at most 1 outgoing edge)
        for (int[] e : edges) {
            out[e[0]] = e[1];
        }
        
        boolean[] visited = new boolean[V];
        int[] time = new int[V];
        
        int maxCycle = -1;
        int timer = 1;
        
        for (int i = 0; i < V; i++) {
            if (visited[i]) continue;
            
            int node = i;
            Map<Integer, Integer> map = new HashMap<>();
            
            // Traverse current path
            while (node != -1 && !visited[node]) {
                visited[node] = true;
                map.put(node, timer++);
                node = out[node];
            }
            
            // Check for cycle
            if (node != -1 && map.containsKey(node)) {
                int cycleLength = timer - map.get(node);
                maxCycle = Math.max(maxCycle, cycleLength);
            }
        }
        
        return maxCycle;
    }
}

Dry Run

Input:

V = 7
edges = [[0,5],[1,0],[2,4],[3,1],[4,6],[5,6],[6,3]]

Graph representation:

0 → 5 → 6 → 3 → 1 → 0

Cycle length = 5

Output:

Edge Cases

No cycle → return -1
Single node with self-loop → cycle length is 1
Disconnected graph → process each component separately

Complexity Analysis

Time Complexity: O(V + E)
Each node is visited once
Space Complexity: O(V)
For visited array and map

Key Takeaways

Functional graphs simplify cycle detection due to single outgoing edges
Timestamp technique helps calculate cycle length efficiently
Avoid revisiting nodes to improve performance

Conclusion

This problem highlights an efficient way to detect cycles in a directed graph with constraints. By leveraging the properties of a functional graph and using a timestamp-based approach, we can compute the longest cycle in linear time. This technique is highly useful in graph traversal problems commonly asked in technical interviews.