Length of Longest Cycle in a Graph

JavaView on GFG

Time: O(V+E)

Space: O(V)

Problem Overview

Find length of longest cycle in directed graph.

Intuition

Find length of longest cycle in directed graph. DFS with distance array tracking depth of discovery.

Algorithm

1DFS with dist[] tracking current DFS depth. On back edge to node v: cycle length = dist[u] - dist[v] + 1.

Common Pitfalls

• Same as LC 2360. Track dist for visited-in-current-DFS nodes. Reset after DFS returns.

Length of Longest Cycle in a Graph.java

Java

// Approach: DFS with timestamps. Track visited time; a back edge to an in-stack node gives cycle length.
// Time: O(V+E) Space: O(V)

import java.util.*;

class Solution {

    void solve(List<List<Integer>> adj, int node, int[] vis, int[] pathvis, int[] timer, int t, int[] max) {
        vis[node] = 1;
        pathvis[node] = 1;
        timer[node] = t;

        for (int nxt : adj.get(node)) {
            if (vis[nxt] == 0)
                solve(adj, nxt, vis, pathvis, timer, t + 1, max);
            else if (pathvis[nxt] == 1)
                max[0] = Math.max(max[0], t - timer[nxt] + 1);
        }
        pathvis[node] = 0;
    }

    public int longestCycle(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= V; i++)
            adj.add(new ArrayList<>());

        for (int[] e : edges)
            adj.get(e[0]).add(e[1]);

        int[] vis = new int[V + 1];
        int[] pathvis = new int[V + 1];
        int[] timer = new int[V + 1];
        Arrays.fill(timer, -1);

        int max1 = -1;

        for (int i = 0; i <= V; i++) {
            if (vis[i] == 0) {
                int[] max = new int[]{-1};
                solve(adj, i, vis, pathvis, timer, 0, max);
                max1 = Math.max(max1, max[0]);
            }
        }
        return max1;
    }
}

Was this solution helpful?