2360. Longest Cycle in a Graph
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
withn
elements, all set toFalse
, 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
(from0
ton-1
). For each node:a. If
vis[i]
isTrue
, the node has already been visited in some previous path exploration, so we skip to the next node.b. If
vis[i]
isFalse
, initialize an empty listcycle
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]`.
-
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 nodei
. -
If the loop ended due to revisiting a node
j
:a. Determine the index
k
incycle
where the nodej
occurs, indicating the start of the cycle. This is done using a generator expression that searches for the first occurrence ofj
incycle
. Ifj
is not found (which won't be the case here sincej
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 indexk
. This gives us the length from the start of the cycle to the end ofcycle
. -
Update
ans
by taking the maximum of the currentans
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. Returnans
.
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 EvaluatorExample 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.
-
Start with initialization:
vis
= [False, False, False, False, False, False]ans
= -1
-
Begin iterating over all nodes:
-
For
i = 0
:vis[0]
isFalse
, so we proceed.- Start an empty list
cycle = []
. - Begin a while loop: Visit node 1, set
vis[0] = True
, append tocycle = [0]
. Visit node 2, setvis[1] = True
, append tocycle = [0, 1]
. Since node 2 has no outgoing edge, the loop ends. - No cycle is detected.
-
For
i = 1
:vis[1]
is alreadyTrue
, so we skip this iteration.
-
For
i = 2
:vis[2]
isFalse
. 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]
isFalse
, so we proceed.- Start an empty list
cycle = []
. - Begin a while loop: Visit node 4, set
vis[3] = True
, append tocycle = [3]
. Visit node 5, setvis[4] = True
, append tocycle = [3, 4]
. Visit node 3 (again), setvis[5] = True
, and append tocycle = [3, 4, 5]
. - We revisited node 3, which indicates a cycle.
- Determine the index
k
incycle
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
andi = 5
:- Both
vis[4]
andvis[5]
areTrue
, so we skip these iterations.
- Both
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 wheren
is the number of nodes. For each node, the inner while loop could potentially run up ton
times in the case of one long cycle. Therefore, the worst-case time complexity of the algorithm isO(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 isn
. - The
cycle
list, in the worst case, might contain all nodes if there is a single cycle involving all nodes, which would also ben
.
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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
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
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 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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.