We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Cycle in a Graph

Difficulty: Hard

Problem Description

You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge. The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from node i, then edges[i] == -1. Return the length of the longest cycle in the graph. If no cycle exists, return -1. A cycle is a path that starts and ends at the same node.

Key Insights

  • Each node can have at most one outgoing edge, making the graph a collection of paths and cycles.
  • A depth-first search (DFS) can be used to explore the graph and detect cycles.
  • We can keep track of visited nodes and their indices to determine the length of cycles.

Space and Time Complexity

Time Complexity: O(n) - Each node is visited at most once. Space Complexity: O(n) - Space used for the visited list and recursion stack.

Solution

To solve the problem, we can use a depth-first search (DFS) approach to explore each node in the graph. We maintain a visited list to track the state of each node (unvisited, visiting, or visited). As we traverse the graph, if we encounter a node that is already in the "visiting" state, we have found a cycle. The length of the cycle can be determined by the difference between the current index and the index at which we first encountered the cycle node. We keep track of the longest cycle found during our traversal.

Code Solutions

def longestCycle(edges):
    n = len(edges)
    visited = [0] * n  # 0 = unvisited, 1 = visiting, 2 = visited
    longest = -1

    def dfs(node, index):
        nonlocal longest
        stack = []
        current_index = index
        while node != -1:
            if visited[node] == 0:  # Unvisited
                visited[node] = 1  # Mark as visiting
                stack.append(node)
                node = edges[node]
            elif visited[node] == 1:  # Found a cycle
                cycle_length = current_index - stack.index(node)
                longest = max(longest, cycle_length)
                break
            else:  # If visited and not part of a cycle
                break
            current_index += 1
        
        while stack:
            visited[stack.pop()] = 2  # Mark as completely visited

    for i in range(n):
        if visited[i] == 0:
            dfs(i, 0)

    return longest
← Back to All Questions