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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int dfs(int node, int *edges, int *visited, int *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] = 1;
11 (*pathLength)++;
12 int cycleLength = dfs(edges[node], edges, visited, recStack, pathLength);
13
14 recStack[node] = 0;
15 (*pathLength)--;
16 return cycleLength;
17}
18
19int longestCycle(int* edges, int edgesSize) {
20 int maxLength = -1;
21 int *visited = (int*)malloc(sizeof(int) * edgesSize);
22 int *recStack = (int*)calloc(edgesSize, sizeof(int));
23 for (int i = 0; i < edgesSize; ++i) visited[i] = -1;
24
25 for (int i = 0; i < edgesSize; ++i) {
26 if (visited[i] == -1) {
27 int pathLength = 0;
28 int cycleLength = dfs(i, edges, visited, recStack, &pathLength);
29 if (cycleLength > maxLength) maxLength = cycleLength;
30 }
31 }
32
33 free(visited);
34 free(recStack);
35 return maxLength;
36}
37
38int main() {
39 int edges[] = {3, 3, 4, 2, 3};
40 int edgesSize = 5;
41 printf("%d\n", longestCycle(edges, edgesSize));
42 return 0;
43}The C solution utilizes DFS to detect cycles. Using arrays for tracking visited nodes and recursion stack during traversal, we calculate the cycle length whenever a cycle is detected by re-entering a node part of the current path.