Сигнал задачи
Когда применять
Нужно упорядочить зависимости в ориентированном ацикличном графе.
Что держать в голове
- Уметь строить входные степени.
- Уметь отличать корректный топологический порядок от сортировки по номеру вершины.
Сложность
- Алгоритм Кана и DFS-вариант работают за O(V + E) времени и используют O(V) дополнительной памяти.
Границы и ошибки
- Если в ответ вошло меньше V вершин, граф содержит цикл; частичный порядок нельзя выдавать как корректное расписание.