2360. Longest Cycle in a Graph

[zeikar]

Problem link

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

Problem Summary

그래프가 주어질 때 가장 길이가 긴 사이클의 길이를 구하는 문제.

Solution

문제 자체는 쉽다. 사이클 중에 가장 긴 길이를 구하면 되는데 직접 구현은 살짝 복잡하긴 하다.

먼저 노드에서 나가는 엣지는 최대 1개이므로 그냥 바로 다음 노드로 건너가면 된다. 다음 노드로 갈 때 level 변수에 1씩 증가하다가 이미 방문한 노드가 있다면 현재 노드와 방문했던 노드의 level의 차이를 반환하면 사이클의 길이가 된다.

하나 주의할 점은 사이클에 속하지 않은 다른 노드에서 이미 방문한 노드를 방문할 때인데, parent 변수를 하나 더 추가해서 해결했다. 더 깔끔한 방법이 있으려나...

Source Code

from collections import deque
from typing import List


class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        level = [-1] * n
        parent = [-1] * n

        def bfs(start):
            queue = deque()
            queue.append(start)
            level[start] = 0
            parent[start] = start

            while queue:
                node = queue.popleft()
                next_node = edges[node]

                if edges[node] == -1:
                    return -1

                if level[next_node] != -1:
                    if parent[next_node] != parent[node]:
                        return -1
                    return level[node] - level[next_node] + 1

                level[next_node] = level[node] + 1
                parent[next_node] = start
                queue.append(next_node)

            return -1

        ans = -1
        for i in range(n):
            if edges[i] != -1 and level[i] == -1:
                ans = max(ans, bfs(i))
        return ans