Sponsored
Sponsored
This approach involves using Depth First Search (DFS) to traverse the graph nodes by starting at each unvisited node. As we explore, we track the nodes in the current path to detect cycles. Whenever we reach a previously visited node that is part of the current path, a cycle is detected, and its length is computed. We keep track of the longest cycle found during the traversal.
Time Complexity: O(n), where n is the number of nodes. We visit each node and edge once.
Space Complexity: O(n), required for the recursion stack and visited nodes array.
1def dfs(node, edges, visited, recStack, pathLength):
2 if node == -1:
3 return -1
4 if recStack[node]:
5 return pathLength - visited[node]
6 if visited[node] != -1:
7 return -1
8
9 visited[node] = pathLength
10 recStack[node] = True
11 pathLength += 1
12 cycleLength = dfs(edges[node], edges, visited, recStack, pathLength)
13
14 recStack[node] = False
15 return cycleLength
16
17def longestCycle(edges):
18 maxLength = -1
19 n = len(edges)
20 visited = [-1] * n
21 recStack = [False] * n
22
23 for node in range(n):
24 if visited[node] == -1:
25 pathLength = 0
26 cycleLength = dfs(node, edges, visited, recStack, pathLength)
27 maxLength = max(maxLength, cycleLength)
28
29 return maxLength
30
31edges = [3, 3, 4, 2, 3]
32print(longestCycle(edges))The Python solution effectively uses recursive DFS exploration with lists for tracking visited nodes and maintaining the recursion path stack. The cycle is determined when a node is revisited in the current path, returning the cycle's length.