- Problem

2360. Longest Cycle in a Graph

유향 그래프에서 형성된 cycle 중 가장 긴 cycle의 길이를 찾는 문제다.

Topological sort와 BFS를 사용했으며, Topological sort를 이용하여 가장자리(사이클이 형성 되지 않은) 노드를 지우며, BFS를 이용하여 형성된 사이클 중 가장 길이가 긴 사이클을 찾아낸다.

- 내 풀이

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        def bfs(start):
            cycle_length = 1
            queue = deque([start])
            visited.add(start)

            while queue:
                current_node = queue.popleft()
                if current_node in graph:
                    neighbor = graph[current_node]
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
                        cycle_length += 1

            return cycle_length

        in_degrees = [0] * len(edges)
        graph = dict()
        for u, v in enumerate(edges):
            if v > -1:
                graph[u] = v
                in_degrees[v] += 1

        queue = deque(i for i in range(len(edges)) if in_degrees[i] == 0)
        visited = set()

        while queue:
            current_node = queue.popleft()
            visited.add(current_node)
            if current_node in graph:
                outgoing_node = graph[current_node]
                in_degrees[outgoing_node] -= 1
                if in_degrees[outgoing_node] == 0:
                    queue.append(outgoing_node)

        if sum(in_degrees) == 0:
            return -1

        longest_cycle = -1

        for i in range(len(edges)):
            if in_degrees[i]:
                longest_cycle = max(bfs(i), longest_cycle)

        return longest_cycle

- 결과

• 시간 복잡도: O(N) (N은 edges의 길이)
• 공간 복잡도: O(N)