2360.Longest Cycle in a Graph

tags: Hard,DFS,Graph

2360. Longest Cycle in a Graph

題目描述

You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.

The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from node i, then edges[i] == -1.

Return the length of the longest cycle in the graph. If no cycle exists, return -1.

A cycle is a path that starts and ends at the same node.

範例

Example 1:

Input: edges = [3,3,4,2,3]
Output: 3
Explanation: The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2.
The length of this cycle is 3, so 3 is returned.

Example 2:

Input: edges = [2,-1,3,1]
Output: -1
Explanation: There are no cycles in this graph.

Constraints:

• n == edges.length
• 2 <= n <= 10⁵
• -1 <= edges[i] < n
• edges[i] != i

解答

C++

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int N = edges.size(), time = 1, ans = -1;
        vector<int> visit_time(N, 0);
        for(int i = 0; i < N; i++) {
            if (visit_time[i]) continue;
            int start = time, cur = i;
            while (cur != -1 && visit_time[cur] == 0) {
                visit_time[cur] = time++;
                cur = edges[cur];
            }
            if (cur != -1 && visit_time[cur] >= start) {
                ans = max(ans, time - visit_time[cur]);
            }
        }
        return ans;
    }
};

Yen-Chi ChenSun, Mar 26, 2023

Python

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        N = len(edges)
        visit_time = [0] * N
        time = 1
        ans = -1
        for node in range(N):
            if visit_time[node] > 0: continue
            start_time = time
            cur = node
            while cur != -1 and visit_time[cur] == 0:
                visit_time[cur] = time
                time += 1
                cur = edges[cur]
            if cur != -1 and visit_time[cur] >= start_time:
                ans = max(ans, time - visit_time[cur])
        return ans

Yen-Chi ChenSun, Mar 26, 2023

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        max_length = -1
        global_visited = set()
        for start, edge in enumerate(edges):
            visited_node = {}
            pos = 0
            node = start
            while edges[node] != -1:
                visited_node[node] = pos
                node = edges[node]
                if node in visited_node:
                    length = pos - visited_node[node] + 1
                    if length > max_length:
                        max_length = length
                    break
                if node in global_visited:
                    break
                pos += 1
                global_visited.add(node)
            global_visited.add(start)

        return max_length

visited_node 原本ㄉ資料結構選錯一直TLEㄏgpwork4uSun, Mar 26, 2023

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        
        inDegree = [0] * n
        for edge in edges:
            if edge != -1:
                inDegree[edge] += 1

        visited = [False] * n

        # Topological Sort
        q = deque()
        for node in range(n):
            if inDegree[node] == 0:
                q.append(node)

        while q:
            node = q.popleft()
            visited[node] = True
            nei = edges[node]
            if nei != -1:
                inDegree[nei] -= 1
                if inDegree[nei] == 0:
                    q.append(nei)

        ans = -1
        for node in range(n):
            if not visited[node]:
                visited[node] = True
                nei = edges[node]
                cnt = 1
                # Iterate in the cycle
                while node != nei:
                    visited[nei] = True
                    nei = edges[nei]
                    cnt += 1
                ans = max(ans, cnt)

        return ans

照著 Reference 的影片做出來ㄉ
Ron ChenMon, Mar 27, 2023

Javascript

function longestCycle(edges) {
  const visited = new Array(edges.length).fill(false);
  const indegree = new Array(edges.length).fill(0);
  for (const edge of edges) {
    indegree[edge]++;
  }

  const stack = [];
  for (let i = 0; i < indegree.length; i++) {
    if (indegree[i] === 0) {
      stack.push(i);
    }
  }

  while (stack.length) {
    const node = stack.pop();
    visited[node] = true;
    indegree[edges[node]]--;
    if (indegree[edges[node]] === 0) {
      stack.push(edges[node]);
    }
  }

  let ans = -1;
  for (let i = 0; i < edges.length; i++) {
    if (visited[i]) continue;
    let count = 0;
    let node = i;
    while (!visited[node]) {
      visited[node] = true;
      node = edges[node];
      count++;
    }

    ans = Math.max(ans, count);
  }

  return ans;
}

照著一行超人給的影片做出來惹
MarsgoatMar 30, 2023

Reference

【每日一题】LeetCode 2360. Longest Cycle in a Graph

回到題目列表