Решить задачу Course Schedule (LeetCode 207)?

LeetCode 207. Можно ли закончить все курсы = нет цикла в directed graph. Topological sort или cycle detection. O(V+E).

# BFS — Kahn's algorithm
from collections import deque
def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1
    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    taken = 0
    while q:
        u = q.popleft()
        taken += 1
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    return taken == numCourses   # False = есть cycle

Альтернатива — DFS с coloring: 0=white, 1=gray (in progress), 2=black (done). Если встречаем gray — cycle. Course Schedule II (210) — вернуть порядок (тот же алгоритм, собрать result).