D
DevExCode

LeetCode 2360: Longest Cycle in a Graph Solution

Master LeetCode problem 2360 (Longest Cycle in a Graph), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To find the longest cycle in a directed graph, we can perform a depth-first search (DFS) from each node to detect cycles. We maintain a visited set to keep track of nodes visited in the current DFS traversal. If we encounter a node that has already been visited in the current traversal, we have found a cycle. We keep track of the length of the cycle and return the maximum length found.

Algorithm:

  1. Initialize a variable maxCycleLength to store the maximum cycle length found.
  2. Iterate through each node in the graph and perform a DFS from that node.
  3. In the DFS function:
    • Keep track of the current path length and visited nodes.
    • If we encounter a node that is already visited in the current traversal, calculate the cycle length and update maxCycleLength.
  4. Return maxCycleLength if a cycle is found, otherwise return -1.

Time Complexity:

The time complexity of this approach is O(n), where n is the number of nodes in the graph.

Space Complexity:

The space complexity is O(n) due to the recursion stack and the visited set.

:

Solution Code

class Solution {
    public int longestCycleInGraph(int[] edges) {
        int maxCycleLength = -1;
        for (int i = 0; i < edges.length; i++) {
            int cycleLength = dfs(i, i, 0, new boolean[edges.length], edges);
            maxCycleLength = Math.max(maxCycleLength, cycleLength);
        }
        return maxCycleLength;
    }
    
    private int dfs(int start, int current, int pathLength, boolean[] visited, int[] edges) {
        if (visited[current]) {
            if (current == start && pathLength > 1) {
                return pathLength;
            }
            return -1;
        }
        visited[current] = true;
        int next = edges[current];
        if (next == -1) {
            visited[current] = false;
            return -1;
        }
        int cycleLength = dfs(start, next, pathLength + 1, visited, edges);
        visited[current] = false;
        return cycleLength;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2360 (Longest Cycle in a Graph)?

This page provides optimized solutions for LeetCode problem 2360 (Longest Cycle in a Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2360 (Longest Cycle in a Graph)?

The time complexity for LeetCode 2360 (Longest Cycle in a Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2360 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2360 in Java, C++, or Python.

Back to LeetCode Solutions