2360. Longest Cycle in a Graph

HardDepth-First SearchGraphTopological Sort
Leetcode Link

Problem Description

You are given a directed graph that consists of n nodes. These nodes are numbered from 0 to n - 1. Each node in the graph has a maximum of one outgoing edge to another node. The representation of this graph is an array edges of size n, where each element edges[i] signifies a directed edge from node i to node edges[i]. If a node i does not have an outgoing edge, then it is indicated by edges[i] == -1.

The task is to determine the length of the longest cycle within the graph. A cycle is a path that begins and ends at the same node. If no cycle exists in the graph, the function should return -1.

Intuition

To find the longest cycle in a directed graph where each node has at most one outgoing edge, we can think of this problem as exploring paths starting from each node until we either revisit a node, indicating a cycle, or reach a node without an outgoing edge.

We proceed as follows:

  1. Iterate over all nodes, using each as a potential cycle starting point.
  2. For each starting node, move to the next node using the outgoing edge and mark each visited node along the path.
  3. Keep tracking visited nodes to recognize when we encounter a cycle.
  4. When we find ourselves at a node that we have visited previously, it indicates the start of a cycle. We measure the length of the path from this node back to itself to calculate cycle length.
  5. If we reach a node without an outgoing edge (edges[i] == -1), we conclude there's no cycle from this path.
  6. We keep track of the maximum length found as we explore cycles from different starting points.

The solution provided uses these steps with an array vis[] to keep track of visited nodes, ensuring each node is processed only once, which helps in maintaining a linear time complexity relative to the number of nodes.

Learn more about Depth-First Search, Graph and Topological Sort patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of these properties could exist for a graph but not a tree?

Solution Approach

The implementation of the solution follows the steps outlined in the intuition:

  1. Initialize a list vis with n elements, all set to False, to record whether a node has been visited (True) or not (False).

  2. Set a variable ans to -1. This will hold the length of the longest cycle found so far.

  3. Iterate over all nodes i (from 0 to n-1). For each node:

    a. If vis[i] is True, the node has already been visited in some previous path exploration, so we skip to the next node.

    b. If vis[i] is False, initialize an empty list cycle to store the path taken starting from the current node (it helps us identify cycles later).

    c. Inside a while loop, visit nodes following the outgoing edges (edges[j]) until you reach a node with no outgoing edge (-1) or revisit a node (indicating a cycle).

    1- For each visited node `j`, set `vis[j]` to `True` and append `j` to the `cycle` list.
2- Update `j` to be the next node to visit, i.e., `j` becomes `edges[j]`.

  4. Once the while loop ends, check if it was due to reaching a node without an outgoing edge. If j == -1, continue to the next node i.

  5. If the loop ended due to revisiting a node j:

    a. Determine the index k in cycle where the node j occurs, indicating the start of the cycle. This is done using a generator expression that searches for the first occurrence of j in cycle. If j is not found (which won't be the case here since j caused the termination of the loop), inf (infinity) is used as the default value.

    b. Calculate the length of the cycle as the difference between the total number of nodes in the cycle list and the index k. This gives us the length from the start of the cycle to the end of cycle.

  6. Update ans by taking the maximum of the current ans and the length of the cycle found in step 5b.

  7. After the loop over all nodes completes, the variable ans holds the length of the longest cycle, or -1 if no cycle was found. Return ans.

The solution makes efficient use of the vis array for marking visited nodes to avoid reprocessing and the cycle list for tracking the current path to identify cycles quickly. The algorithm's complexity is O(n) since each node and edge is visited at most once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the steps outlined above.

Suppose we are given the following directed graph as an edges array:

1edges = [1, 2, -1, 4, 5, 3]

This graph has 6 nodes (n = 6). The edges array implies:

  • Node 0 has an outgoing edge to node 1.
  • Node 1 has an outgoing edge to node 2.
  • Node 2 has no outgoing edge (indicated by -1).
  • Node 3 has an outgoing edge to node 4.
  • Node 4 has an outgoing edge to node 5.
  • Node 5 has an outgoing edge to node 3.

We are going to determine the length of the longest cycle.

  1. Start with initialization:

    • vis = [False, False, False, False, False, False]
    • ans = -1

  2. Begin iterating over all nodes:

  3. For i = 0:

    • vis[0] is False, so we proceed.
    • Start an empty list cycle = [].
    • Begin a while loop: Visit node 1, set vis[0] = True, append to cycle = [0]. Visit node 2, set vis[1] = True, append to cycle = [0, 1]. Since node 2 has no outgoing edge, the loop ends.
    • No cycle is detected.

  4. For i = 1:

    • vis[1] is already True, so we skip this iteration.

  5. For i = 2:

    • vis[2] is False. However, node 2 has no outgoing edge (edges[2] == -1), so we can't start a cycle from here.
    • Set vis[2] = True.

  6. For i = 3:

    • vis[3] is False, so we proceed.
    • Start an empty list cycle = [].
    • Begin a while loop: Visit node 4, set vis[3] = True, append to cycle = [3]. Visit node 5, set vis[4] = True, append to cycle = [3, 4]. Visit node 3 (again), set vis[5] = True, and append to cycle = [3, 4, 5].
    • We revisited node 3, which indicates a cycle.
    • Determine the index k in cycle where node 3 occurs, k = 0.
    • Calculate the length of the cycle: len(cycle) - k = 3 - 0 = 3.
    • Update ans = max(-1, 3) = 3.

  7. For i = 4 and i = 5:

    • Both vis[4] and vis[5] are True, so we skip these iterations.

After completing the loop, we find that ans = 3, which indicates that the longest cycle in the graph has a length of 3. Hence, the function would return 3.

Solution Implementation

1from typing import List
2
3class Solution:
4    def longestCycle(self, edges: List[int]) -> int:
5        # Initialize the number of nodes in the edge list
6        num_nodes = len(edges)
7        # Create a visitation status list to keep track of visited nodes
8        visited = [False] * num_nodes
9        # Initialize the answer to -1, which stands for no cycle found
10        longest_cycle_length = -1
11      
12        # Iterate over each node
13        for node in range(num_nodes):
14            # Skip processing if the current node has been visited
15            if visited[node]:
16                continue
17          
18            # Initialize the node for cycle checking
19            current_node = node
20            # Initialize list to store nodes in the current cycle
21            node_cycle = []
22          
23            # Continue traversing the graph unless we hit a node
24            # that points to -1 or it has been visited
25            while current_node != -1 and not visited[current_node]:
26                # Mark the node as visited
27                visited[current_node] = True
28                # Append current node to the cycle
29                node_cycle.append(current_node)
30                # Move to the next node in the graph
31                current_node = edges[current_node]
32          
33            # If the end of an edge chain points to -1, a cycle isn't possible
34            if current_node == -1:
35                continue
36          
37            # Calculate the length of the cycle. To do this, we find the index of
38            # the node that we revisited which caused the cycle detection
39            cycle_length = len(node_cycle)
40            # Find the starting index of the cycle within node_cycle list
41            cycle_start_index = next((k for k in range(cycle_length) if node_cycle[k] == current_node), float('inf'))
42            # Update the longest_cycle_length with the maximum
43            longest_cycle_length = max(longest_cycle_length, cycle_length - cycle_start_index)
44      
45        # Return the length of the longest cycle, or -1 if no cycle is found
46        return longest_cycle_length
47
1class Solution {
2    public int longestCycle(int[] edges) {
3        int numberOfNodes = edges.length;
4        boolean[] visited = new boolean[numberOfNodes]; // This array holds whether a node has been visited
5        int maxCycleLength = -1; // Store the length of the longest cycle found, -1 if none
6      
7        // Iterate through all nodes
8        for (int startNode = 0; startNode < numberOfNodes; ++startNode) {
9            // Skip if the current node has been visited
10            if (visited[startNode]) {
11                continue;
12            }
13            int currentNode = startNode;
14            List<Integer> cycle = new ArrayList<>(); // Current potential cycle path
15          
16            // Traverse the graph until a loop is found or there are no more nodes to visit
17            for (; currentNode != -1 && !visited[currentNode]; currentNode = edges[currentNode]) {
18                visited[currentNode] = true; // Mark this node as visited
19                cycle.add(currentNode); // Add the current node to the cycle
20            }
21          
22            // If a loop is detected, calculate its length
23            if (currentNode != -1) {
24                // Find the index of the node where the loop starts
25                for (int cycleIndex = 0; cycleIndex < cycle.size(); ++cycleIndex) {
26                    if (cycle.get(cycleIndex) == currentNode) {
27                        // Cycle length is the size of the cycle minus the index of the start node of the loop
28                        maxCycleLength = Math.max(maxCycleLength, cycle.size() - cycleIndex);
29                        break;
30                    }
31                }
32            }
33        }
34        return maxCycleLength; // Return the length of the longest cycle found
35    }
36}
37
1class Solution {
2public:
3    int longestCycle(vector<int>& edges) {
4        int numNodes = edges.size();
5        vector<bool> visited(numNodes, false);
6        int longestCycleLength = -1;  // Initialize with -1 to represent no cycle found.
7
8        // Loop through each node to find the longest cycle, if any.
9        for (int start = 0; start < numNodes; ++start) {
10            // Skip if the node has been visited.
11            if (visited[start]) {
12                continue;
13            }
14
15            // Use two pointers to traverse the graph and record the cycle.
16            int current = start;
17            vector<int> cycleNodes;
18
19            // Explore the graph to find a cycle.
20            for (; current != -1 && !visited[current]; current = edges[current]) {
21                visited[current] = true; // Mark the node as visited.
22                cycleNodes.push_back(current); // Add to cycle list.
23            }
24
25            // If we did not encounter a cycle, continue with the next node.
26            if (current == -1) {
27                continue;
28            }
29          
30            // Check the recorded nodes to determine the cycle's length.
31            for (int idx = 0; idx < cycleNodes.size(); ++idx) {
32                // Find the start index of the cycle within the cycle list.
33                if (cycleNodes[idx] == current) {
34                    // Calculate and store the maximum cycle length found so far.
35                    longestCycleLength = max(longestCycleLength, static_cast<int>(cycleNodes.size() - idx));
36                    break; // Break as we found the cycle start point.
37                }
38            }
39        }
40        return longestCycleLength; // Return the longest cycle length found.
41    }
42};
43
1// Function to find the length of the longest cycle in a graph represented as an array of edges
2function longestCycle(edges: number[]): number {
3    const nodeCount = edges.length;  // Total number of nodes in the graph
4    const visited = new Array(nodeCount).fill(false);  // An array to keep track of visited nodes
5    let longestCycleLength = -1;  // Initialize the length of the longest cycle as -1 (indicating no cycles)
6
7    // Iterate through each node to check for cycles
8    for (let i = 0; i < nodeCount; ++i) {
9        // Skip already visited nodes
10        if (visited[i]) {
11            continue;
12        }
13
14        let currentNode = i;  // Start from the current node
15        const currentCycle: number[] = [];  // List to keep track of the current cycle
16
17        // Traverse the graph using the edges until a visited node or the end (-1) is reached
18        while (currentNode != -1 && !visited[currentNode]) {
19            // Mark the current node as visited
20            visited[currentNode] = true;
21
22            // Add the current node to the cycle list
23            currentCycle.push(currentNode);
24
25            // Move to the next node by following the edge
26            currentNode = edges[currentNode];
27        }
28
29        // Check if the traversal ended on an already visited node, indicating a cycle
30        if (currentNode == -1) {
31            // If no cycle is found, move on to the next node
32            continue;
33        }
34
35        // If a cycle is found, calculate the length of the cycle
36        for (let nodeIndex = 0; nodeIndex < currentCycle.length; ++nodeIndex) {
37            // Check if the cycle loops back to the starting node
38            if (currentCycle[nodeIndex] == currentNode) {
39                // Update the length of the longest cycle if the current cycle is longer
40                longestCycleLength = Math.max(longestCycleLength, currentCycle.length - nodeIndex);
41                break;  // Exit the loop as the cycle length has been found
42            }
43        }
44    }
45
46    // Return the length of the longest cycle found in the graph
47    return longestCycleLength;
48}
49
50// Note: The edges array represents a directed graph where each position i in the array
51// is a node, and its value edges[i] is the node that i is directed to (-1 if it has no outgoing edges).
52
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

Time Complexity

The given Python code aims to find the length of the longest cycle in a directed graph where the list edges represents adjacency information: an index i points to edges[i].

For each node, the algorithm checks whether it has been visited. If a node is unvisited, it starts a DFS-like traversal by following edges until it either hits a previously visited node (indicating the beginning of a cycle) or an end (-1).

  • The worst-case scenario for time complexity occurs when each node is part of a complex cycle. The outer loop runs n times where n is the number of nodes. For each node, the inner while loop could potentially run up to n times in the case of one long cycle. Therefore, the worst-case time complexity of the algorithm is O(n^2).

Space Complexity

The space complexity of the algorithm is determined by the additional space used:

  • The vis list is used to keep track of visited nodes, and its size is n.
  • The cycle list, in the worst case, might contain all nodes if there is a single cycle involving all nodes, which would also be n.

Hence, the overall space complexity is O(n) due to the storage required for the vis and cycle lists, which grow linearly with the number of nodes n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Topological Sort Introduction

Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ