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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Cycle in a Graph

Number: 2439

Difficulty: Hard

Paid? No

Companies: Juspay, Microsoft, Amazon

Problem Description

Given a directed graph with n nodes (numbered from 0 to n-1) where each node has at most one outgoing edge (represented by the array edges), find the length of the longest cycle present in the graph. If there is no cycle in the graph, return -1.

Key Insights

  • Each node can have at most one outgoing edge, which means the graph is composed of chains and possibly cycles.
  • A cycle is detected when, during the traversal from a starting point, a node is revisited.
  • Keeping track of the traversal path and the order in which nodes are visited allows us to compute the cycle’s length easily by subtracting the indices.
  • Once a node has been fully processed (visited in any traversal), it can be skipped in future traversals to ensure linear time complexity.
  • Using a dictionary (or map/array) to record the index of each node in the current path is essential to determine the cycle length when a revisited node is encountered.

Space and Time Complexity

Time Complexity: O(n) – Each node is visited at most once. Space Complexity: O(n) – For tracking visited nodes and indices in the current path.

Solution

We iterate over all nodes. For each unvisited node, we perform a traversal following its directed edge path. A map/dictionary is used to store the index (or step count) when a node is first encountered in the current traversal. If we meet a node that is already in the current mapping, then we have detected a cycle; the cycle's length is determined by subtracting the stored index from the current step index. After finishing a traversal from a node, mark all nodes in that path as visited so that they are not reprocessed. This method efficiently identifies cycles and calculates their lengths while ensuring that each node is processed only once.

Code Solutions

def longestCycle(edges):
    n = len(edges)
    visited = [False] * n  # To mark nodes that have been fully processed
    longest = -1

    # Traverse each node as a starting point if not already visited
    for i in range(n):
        if visited[i]:
            continue
        curr = i
        step = 0
        # local_map tracks the node and its arrival step in the current chain
        local_map = {}
        # Traverse through the directed edges
        while curr != -1 and curr not in local_map:
            if visited[curr]:
                break  # This node is already processed from a previous traversal
            local_map[curr] = step
            step += 1
            curr = edges[curr]
        # Check if we detected a cycle
        if curr != -1 and curr in local_map:
            cycle_length = step - local_map[curr]
            longest = max(longest, cycle_length)
        # Mark all nodes in this traversal as visited
        for node in local_map:
            visited[node] = True
    return longest

# Example usage:
print(longestCycle([3,3,4,2,3]))  # Expected output: 3
print(longestCycle([2,-1,3,1]))   # Expected output: -1
← Back to All Questions