테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== Course Schedule ======
  * 그래프 이론에서 대표적인 문제 중 하나인, 방향 그래프에서 사이클의 존재 여부를 확인하는 문제.

===== 풀이 =====
  * [[ps:위상 정렬]] 참고

===== 코드 =====
<dkpr py>
"""Solution code for "LeetCode 22. Course Schedule".

- Problem link: https://leetcode.com/problems/course-schedule/
- Solution link: http://www.teferi.net/ps/problems/leetcode/207
"""

from typing import AbstractSet, List, Sequence


def topologicalSort(graph: Sequence[AbstractSet[int]]) -> List[int]:
    """Returns a list of nodes in topologically sorted order."""
    indegrees = [0] * len(graph)
    for successors in graph:
        for v in successors:
            indegrees[v] += 1

    stack = [u for u, indegree in enumerate(indegrees) if indegree == 0]
    result = []
    while stack:
        u = stack.pop()
        result.append(u)
        for v in graph[u]:
            indegrees[v] -= 1
            if indegrees[v] == 0:
                stack.append(v)

    if len(result) != len(graph):
        raise ValueError('found a cycle')
    return result


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [set() for _ in range(numCourses)]
        for u, v in prerequisites:
            graph[u].add(v)
        try:
            topologicalSort(graph)
            return True
        except ValueError:
            return False
</dkpr>