2360. Longest Cycle in a Graph

HardDepth-First SearchGraphTopological Sort

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.

Flowchart Walkthrough

To determine the appropriate algorithm for solving LeetCode problem 2360, "Longest Cycle in a Graph," let's analyze it using the Flowchart. Here’s a step-by-step explanation:

Is it a graph?

Yes: The problem specifically deals with a graph, where each node points to exactly one other node.

Is it a tree?

No: Since cycles are possible in the given scenario (a node can eventually lead back to itself), it's not a tree structure.

Is the problem related to directed acyclic graphs (DAGs)?

No: The presence of cycles indicates that the graph is not acyclic.

Is the problem related to shortest paths?

No: The problem asks for the longest cycle, not the shortest path between points.

Does the problem involve connectivity?

Yes: The problem requires exploring connections to determine cycles in the graph, which involves analyzing how nodes are connected to one another.

Is the graph weighted?

No: The description doesn't imply any weights associated with the edges; rather, it's focused on the structure of the graph.

Does the problem have small constraints?

Yes: Considering that we're looking for cycles specifically and the problem can involve detailed state tracking (not specified as small in given context, generally DFS is well-suited for problems involving cycles and detailed traversals).

Since the problem has constraints that suggest a manageable graph size and complexity (assuming from standard problem constraints on Leetcode), DFS or Backtracking are suitable as they efficiently explore all paths for cycles without revisiting nodes unnecessarily. DFS is particularly effective because it explores each vertex and edge once, which is critical in finding the longest cycle in a graph.

Conclusion: Based on the Flowchart, Depth-First Search (DFS) or DFS/backtracking are recommended for exploring all possible nodes and efficiently checking for cycles in the graph while making sure each node within a potential cycle is only visited once per traversal.

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:

Iterate over all nodes, using each as a potential cycle starting point.
For each starting node, move to the next node using the outgoing edge and mark each visited node along the path.
Keep tracking visited nodes to recognize when we encounter a cycle.
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.
If we reach a node without an outgoing edge (edges[i] == -1), we conclude there's no cycle from this path.
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.

Solution Approach

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

Initialize a list vis with n elements, all set to False, to record whether a node has been visited (True) or not (False).
Set a variable ans to -1. This will hold the length of the longest cycle found so far.

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).

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

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.
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.
Update ans by taking the maximum of the current ans and the length of the cycle found in step 5b.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

edges = [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.

Start with initialization:
- vis = [False, False, False, False, False, False]
- ans = -1
Begin iterating over all nodes:
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.
For i = 1:
- vis[1] is already True, so we skip this iteration.
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.
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.
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

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.

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

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know