Length of Longest Cycle in a Graph

JavaView on GFG

Time: O(V+E)

Space: O(V)

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?