GoCalf Calf 的自留地 · 昙花一现

2360. Longest Cycle in a Graph

Calf

Problem

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.

https://leetcode.com/problems/longest-cycle-in-a-graph/

Example 1:

case1
case1

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:

case2
case2

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

Test Cases

python 
class Solution:
    def longestCycle(self, edges: List[int]) -> int:
solution_test.py下载完整源码
py 
import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('edges, expected', [
    ([3,3,4,2,3], 3),
    ([2,-1,3,1], -1),

    ([3,4,0,2,-1,2], 3),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, edges, expected):
    assert sol.longestCycle(edges) == expected

Thoughts

任意图求最大环，类似于计算哈密顿回路，是 NP 难问题。本题是加了限定条件的图。

相当于简版的 2127. Maximum Employees to Be Invited to a Meeting，只是每个顶点的入度从严格为 1 变为小于等于 1，然后也不需要计算长度为 2 的环两头的拉链长度。

直接在 problem 2127 第二个方法——拓扑排序 的代码上改一改就行了。

Code

solution.py下载完整源码
py 
from collections import deque


class Solution:
    def longestCycle(self, edges: list[int]) -> int:
        max2 = lambda a, b: a if a >= b else b
        n = len(edges)
        in_degrees = [0] * n
        for _, v in enumerate(edges):
            if v >= 0: in_degrees[v] += 1

        zeros = deque(u for u in range(n) if in_degrees[u] == 0)
        while len(zeros):
            u = zeros.popleft()
            v = edges[u]
            if v < 0: continue
            in_degrees[v] -= 1
            if in_degrees[v] == 0:
                zeros.append(v)

        max_cycle = -1
        for u in range(n):
            if in_degrees[u] == 0: continue
            length = 1
            v = edges[u]
            while v != u:
                in_degrees[v] = 0
                length += 1
                v = edges[v]

            max_cycle = max2(max_cycle, length)

        return max_cycle

Simpler

之前在 problem 2127 中拓扑排序是为了能计算出「环上的每个顶点，指向它的无环边的最大长度」。本题并不需要这个信息，除了在拓扑排序过程中不在记录 d(u) 值，整个处理逻辑都可以进一步简化。

假设从一个顶点 u 出发，如果会进入环路，则一定会遇到出发后曾经见过的某个顶点，不妨设每一秒移动一次，那么两次遇到同一个顶点的时间之差，就是环长。

如下图，从 u 出发，记出发时间为 t = 1。第一次经过 v 的时间是 t = 3，到 t = 8 时再次访问 v，说明有环，且环长为 8 - 3 = 5。

为了避免重复处理，每个顶点经过的时间都记录下来，曾经访问过的顶点就不再访问了。

但是像上图那样，当第二次访问到 v，发现 v 已经被访问过，需要能够知道是本轮（从 u 出发后）才访问的，还是之前就已经访问过。一个简单的方法就是让时间一直递增下去，这样本轮的出发时刻就一定比之前所有节点被访问的时刻都靠后。

时间和空间复杂度都是 O(n)。

solution2.py下载完整源码
py 
class Solution:
    def longestCycle(self, edges: list[int]) -> int:
        max2 = lambda a, b: a if a >= b else b
        n = len(edges)
        max_cycle = -1
        visits = [0] * n # visits[u]: the first time visiting node u.
        time = 1
        for u in range(n):
            if visits[u]: continue

            v = u
            while v >= 0 and not visits[v]:
                visits[v] = time
                time += 1
                v = edges[v]

            if v >= 0 and visits[v] >= visits[u]: # v is visited twice starting from u.
                max_cycle = max2(max_cycle, time - visits[v])

        return max_cycle

评论需要 JavaScript。