Skip to content

2360. Longest Cycle in a Graph 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int longestCycle(vector<int>& edges) {
    int ans = -1;
    int time = 1;
    vector<int> timeVisited(edges.size());

    for (int i = 0; i < edges.size(); ++i) {
      if (timeVisited[i])
        continue;
      const int startTime = time;
      int u = i;
      while (u != -1 && !timeVisited[u]) {
        timeVisited[u] = time++;
        u = edges[u];  // Move to the next node.
      }
      if (u != -1 && timeVisited[u] >= startTime)
        ans = max(ans, time - timeVisited[u]);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int longestCycle(int[] edges) {
    int ans = -1;
    int time = 1;
    int[] timeVisited = new int[edges.length];

    for (int i = 0; i < edges.length; ++i) {
      if (timeVisited[i] > 0)
        continue;
      final int startTime = time;
      int u = i;
      while (u != -1 && timeVisited[u] == 0) {
        timeVisited[u] = time++;
        u = edges[u]; // Move to the next node.
      }
      if (u != -1 && timeVisited[u] >= startTime)
        ans = Math.max(ans, time - timeVisited[u]);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def longestCycle(self, edges: list[int]) -> int:
    ans = -1
    time = 1
    timeVisited = [0] * len(edges)

    for i, edge in enumerate(edges):
      if timeVisited[i]:
        continue
      startTime = time
      u = i
      while u != -1 and not timeVisited[u]:
        timeVisited[u] = time
        time += 1
        u = edges[u]  # Move to the next node.
      if u != -1 and timeVisited[u] >= startTime:
        ans = max(ans, time - timeVisited[u])

    return ans