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 <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int dfs(int node, vector<int>& edges, vector<int>& visited, vector<int>& recStack, int& pathLength) {
7 if (node == -1) return -1;
8 if (recStack[node]) return pathLength - visited[node];
9 if (visited[node] != -1) return -1;
10
11 visited[node] = pathLength;
12 recStack[node] = 1;
13 pathLength++;
14 int cycleLength = dfs(edges[node], edges, visited, recStack, pathLength);
15
16 recStack[node] = 0;
17 pathLength--;
18 return cycleLength;
19}
20
21int longestCycle(vector<int>& edges) {
22 int maxLength = -1;
23 int n = edges.size();
24 vector<int> visited(n, -1);
25 vector<int> recStack(n, 0);
26
27 for (int i = 0; i < n; ++i) {
28 if (visited[i] == -1) {
29 int pathLength = 0;
30 int cycleLength = dfs(i, edges, visited, recStack, pathLength);
31 if (cycleLength > maxLength) maxLength = cycleLength;
32 }
33 }
34
35 return maxLength;
36}
37
38int main() {
39 vector<int> edges = {3, 3, 4, 2, 3};
40 cout << longestCycle(edges) << endl;
41 return 0;
42}The C++ solution uses DFS for cycle detection, employing vectors for tracking visited nodes and call stack, applying similar logic to the C solution, while taking advantage of C++ facilities for vector operations.