위상 정렬

from collections import deque

graph = {                                      # 간선 u → v 는 "u가 v보다 먼저"
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['E', 'F'],
    'E': [],
    'F': [],
}

def kahn(graph):
    indeg = {v: 0 for v in graph}
    for v in graph:
        for w in graph[v]:
            indeg[w] += 1                    # 진입 차수 계산
    q = deque(v for v in graph if indeg[v] == 0)
    order = []
    while q:
        v = q.popleft()
        order.append(v)
        for w in graph[v]:
            indeg[w] -= 1                    # v에서 나가는 간선을 지운다
            if indeg[w] == 0:
                q.append(w)
    return order if len(order) == len(graph) else None

print(kahn(graph))                         # ['A', 'B', 'C', 'D', 'E', 'F']

cyc = dict(graph)
cyc['E'] = ['A']                           # A → C → E → A 사이클
print(kahn(cyc))                           # None

def dfs_sort(graph):
    state = {}                                  # 1: 탐색 중, 2: 종료
    out = []

    def visit(v):
        state[v] = 1
        for w in graph[v]:
            if state.get(w) == 1:
                raise ValueError('cycle')      # 탐색 중인 정점으로 되돌아옴
            if w not in state:
                visit(w)
        state[v] = 2
        out.append(v)                         # 끝나는 순서대로 기록

    for v in graph:
        if v not in state:
            visit(v)
    return out[::-1]                           # 뒤집으면 위상 순서

print(dfs_sort(graph))                     # ['B', 'D', 'F', 'A', 'C', 'E']
try:
    dfs_sort(cyc)
except ValueError as e:
    print('ValueError', e)               # ValueError cycle

from graphlib import TopologicalSorter, CycleError

deps = {                                       # 키: 작업, 값: 먼저 끝나야 하는 작업들
    'C': ['A', 'B'],
    'D': ['B'],
    'E': ['C', 'D'],
    'F': ['D'],
}
print(list(TopologicalSorter(deps).static_order()))
# ['A', 'B', 'C', 'D', 'E', 'F']

deps['A'] = ['E']                           # 사이클 추가
try:
    list(TopologicalSorter(deps).static_order())
except CycleError:
    print('CycleError')                   # CycleError