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.
1using System;
2
3public class LongestCycleGraph {
4 private static int Dfs(int node, int[] edges, int[] visited, bool[] recStack, int pathLength) {
5 if (node == -1) return -1;
6 if (recStack[node]) return pathLength - visited[node];
7 if (visited[node] != -1) return -1;
8
9 visited[node] = pathLength;
10 recStack[node] = true;
11 pathLength++;
12 int cycleLength = Dfs(edges[node], edges, visited, recStack, pathLength);
13
14 recStack[node] = false;
15 return cycleLength;
16 }
17
18 public static int LongestCycle(int[] edges) {
19 int n = edges.Length;
20 int maxLength = -1;
21 int[] visited = new int[n];
22 Array.Fill(visited, -1);
23 bool[] recStack = new bool[n];
24
25 for (int i = 0; i < n; i++) {
26 if (visited[i] == -1) {
27 int pathLength = 0;
28 int cycleLength = Dfs(i, edges, visited, recStack, pathLength);
29 maxLength = Math.Max(maxLength, cycleLength);
30 }
31 }
32
33 return maxLength;
34 }
35
36 public static void Main() {
37 int[] edges = {3, 3, 4, 2, 3};
38 Console.WriteLine(LongestCycle(edges));
39 }
40}The C# implementation follows the DFS strategy with similar logic, utilizing arrays for node tracking and handling recursion. It identifies cycles via re-entering existing nodes on the recursion stack.