Longest Cycle in a Graph LeetCode solution in C++

1
class Solution {
2
 public:
3
  int longestCycle(vector<int> &edges) {
4
    int ans = -1;                          // Initialize the answer to -1
5
    int time = 1;                          // Initialize the current time step to 1
6
    vector<int> timeVisited(edges.size()); // Initialize a vector to store the time at which each
7
                                           // node was first visited
8

9
    // Iterate through each node in the graph
10
    for (int i = 0; i < edges.size(); ++i) {
11
      if (timeVisited[i]) // If the node has already been visited, skip it
12
        continue;
13
      const int startTime = time; // Record the start time of the current traversal
14
      int u = i;                  // Initialize the current node to the ith node
15
      // Traverse the graph until the end of the path is reached or a visited
16
      // node is encountered
17
      while (u != -1 && !timeVisited[u]) {
18
        timeVisited[u] = time++; // Record the current time step and increment time
19
        u = edges[u];            // Move to the next node in the path
20
      }
21
      // If a cycle is found that includes the current node, update the answer
22
      if (u != -1 && timeVisited[u] >= startTime) ans = max(ans, time - timeVisited[u]);
23
    }
24

25
    return ans; // Return the length of the longest cycle found
26
  }
27
};