course-schedule-ii.md

210. Course Schedule II

Задача

Дана университетская программа. Курсы могут иметь зависимости. Нужно найти порядок курсов, в котором возможно пройти всю программу.

A roadmap to becoming a web developer in 2017

Задача на LeetCode.

Вопросы

1. Уточнение входных данных:

   • Можете ли вы уточнить формат входных данных? Курсы даны по названиям, сколько всего может быть курсов?

     Всего есть N различных курсов в программе, можно опустить их названия и ссылаться по номеру. Список зависимостей задается в формате [x, y] где x , y числа в отрезке [0, N - 1] — для того чтобы закончить курс x , сперва нужно закончить курс y .

2. Ограничения задачи:

   • Какое минимальное и максимальное число курсов? Может ли быть ноль курсов?

     В отрезке 1 <= N <= 2000 . Считаем, что «пустых» программ не бывает.

   • Могут ли быть циклические зависимости?

     Да. В таком случае нужно вернуть пустой список.

3. Ожидаемый результат:

   • Что делать если возможно несколько вариантов как пройти всю программу?

     Вернуть любой из них.

   • В каком формате ожидается вывод?

     Список курсов в определенном порядке, который позволит закончить программу.

Задавая подобные вопросы, кандидат не только уточняет свое понимание задачи, но и показывает интервьюеру свои навыки в поиске решений проблем.

Примеры

Сперва определяем сигнатуру функции, далее спрашиваем несколько примеров с объяснениями: findOrder(n, prerequisites) .

1. Пример 1:

• findOrder(2, [[1, 0]]) —> [0, 1]
• Сперва нужно взять нулевой курс, затем первый (так как первый зависит от нулевого).

1. Пример 2:

• findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) —> [0, 2, 1, 3]
• Есть несколько возможных путей: [0, 1, 2, 3], [0, 2, 1, 3] — нужно вернуть любой из них.

Решение

Думаю, к этому моменту уже сложилось понимание, что это граф из N вершин, с ребрами, которым можно построить по списку зависимостей.

Представим, что мы построили граф в виде списка смежности — это когда каждой вершине соответствует список ее «зависимостей», то есть вершин, с которыми она соединяется ребрами.

В случае из второго примера список выглядит так:

0: [1, 2]
1: [3]
2: [3]
3: []

Первая интуция и немного теории графов (на пальцах)

Воткнувшись в любой узел в графе не получится начать с него, ведь у него могут быть зависимости, их надо сперва разрешить. Какие узлы могуть быть «началом»? Те, у которых нет зависимостей.

Мы приходим к определению степеней вершин, входящих (indegree) и исходящих (outdegree), то есть сколько есть входящих и исходящих из вершины ребер.

В данной задаче мы будем говорить про входящую степень, поэтому далее — просто степень.

Сперва нужно посчитать степени, и далее начинать поиск от вершин со степенями ноль (которые называются изолированными).

Представим, что мы нашли первый изолированный узел и начинаем случайный поиск в глубину. В какой-то момент нам может встретиться узел у которого есть свои зависимости, и нужно сперва их разрешить — дальше идти нельзя.

Хм... получается, начинать надо с узлов с меньшим числом зависимостей. То есть как бы отсортировать по степени. Тогда к моменту проверки последних узлов, у которых больше всего зависимостей, мы их гарантированно разрешим раньше, то есть не будет ситуации выше.

Интуитивно мы приходим к понятию топологической сортировки.

Формально топологическая сортировка это как раз такое линейное представление узлов графа, что если в графе существует направленное ребро от вершины u к вершине v , то вершина u идет перед вершиной v .

Алгоритм Кана

Есть несколько вариантов как реализовать топологическую сортировку: можно рекурсивно через поиск в глубину, можно с помощью очереди через алгоритм Кана.

Описание выше, на самом деле, уже складывается в алгоритм Кана.

• находим степени всех узлов
• заводим очередь, кладем туда изолированные узлы
• пока очередь не пустая
  • снимаем очередной узел с начала очереди, кладем его в ответ
  • уменьшаем степени соседей на 1 — мы как бы вынимаем узел из графа, а значит у соседей становится на одно ребро меньше
    • если степень узла стала равна нулю кладем его в конец очереди

Таким образом, в ответе узлы окажутся отсортированными от меньшей к большей степени, то есть от курсов без зависимостей вовсе, до курсов с максимальным количеством зависимостей.

Чем мне нравится алгоритм Кана — его удобно прогнать на доске на конкретном примере, убедиться, что это работает. На собеседованиях, завершающим этапом, после кода, должно идти тестирование.

Циклы

В условии сказано, что возможны циклические зависимости. Каким образом алгоритм топологической сортировки отработает в таком случае?

В таком случае какой-то порядок вершин, конечно, окажется в ответе, но это фейк 😊 Очередь закончится раньше, чем обработает все вершины. Это и достаточно проверить, чтобы сказать был ли цикл в графе. Если в ответе есть все вершины — значит сортировка дошла до конца, не встретив циклов.

Сложность O(V + E) , где V , E - количество вершин и ребер соответственно, так как в каждую вершину и ребро мы смотрим один раз.

P. S. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.