Java  

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:

5

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.

Membership not found