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.
1function dfs(node, edges, visited, recStack, pathLength) {
2 if (node === -1) return -1;
3 if (recStack[node]) return pathLength - visited[node];
4 if (visited[node] !== -1) return -1;
5
6 visited[node] = pathLength;
7 recStack[node] = true;
8 pathLength++;
9 const cycleLength = dfs(edges[node], edges, visited, recStack, pathLength);
10
11 recStack[node] = false;
12 return cycleLength;
13}
14
15function longestCycle(edges) {
16 let maxLength = -1;
17 const n = edges.length;
18 const visited = Array(n).fill(-1);
19 const recStack = Array(n).fill(false);
20
21 for (let i = 0; i < n; i++) {
22 if (visited[i] === -1) {
23 let pathLength = 0;
24 const cycleLength = dfs(i, edges, visited, recStack, pathLength);
25 maxLength = Math.max(maxLength, cycleLength);
26 }
27 }
28 return maxLength;
29}
30
31const edges = [3, 3, 4, 2, 3];
32console.log(longestCycle(edges));The JavaScript approach involves a DFS function calling mechanism, leveraging arrays to register visited nodes and track the recursion path, determining cycle lengths through path node re-entry.