Где применяется
1. Задача
Ты одеваешься. Носки раньше ботинок. Рубашка раньше пиджака. Бельё раньше брюк. Ни одно правило не говорит «надень меня третьим». Каждое говорит только «надень меня после вот этого». Нужно найти полный порядок, который не нарушает ни одного правила.
Программы решают такую задачу постоянно. Менеджер пакетов ставит библиотеки, и каждую надо ставить после всех библиотек, которые ей нужны. Система сборки компилирует файлы, и файл, который импортирует другой, собирается после него. У курсов в учебном каталоге есть пререквизиты (курсы, которые надо пройти раньше). Везде один и тот же запрос: дан набор правил «X должно идти раньше Y», выдай один порядок, в котором выполнены все правила.
Иногда такого порядка нет. Если A нужен B, а B нужен A, ни один порядок не подойдёт. Хорошая программа должна это заметить и сообщить, а не крутиться вечно.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитtopoSort(6, [[1, 2], [3], [3, 5], [4, 5], [], []])Стрелка u → v значит, что u должна выполниться раньше v. Считаем входящие стрелки у каждой задачи.
Как узнать
Эти слова в условии значат этот паттерн
- задача должна идти перед другой
- порядок, соблюдающий зависимости
- обнаружить цикл в предпосылках
- порядок сборки / расписание курсов / порядок установки
- ориентированный граф, X должен произойти перед Y
Похоже, но не то
- Обход графа BFS / DFS (Graph BFS / DFS)
Обычный обход посещает вершины в любом удобном порядке. Здесь порядок и есть ответ.
- Компоненты связности (Connected components)
Компоненты не смотрят на направление и только группируют вершины. Здесь направление задаёт весь ответ.
- Система непересекающихся множеств (Union-find (disjoint set))
Она считает любое ребро ненаправленным. Направление здесь и есть самое главное.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Правило жадное: берите всё, у чего не осталось долгов. Удаление вершины не может добавить зависимость.
V вершин и E рёбер дают O(V + E). Каждое ребро убирается ровно один раз.
На LeetCode
Задачи, где нужно расставить задачи в порядке, который уважает зависимости, или сказать, что такого порядка нет. Посчитай входящую степень, начни с узлов, где она равна нулю, убирай их по одному, и если какие-то узлы так и не дошли до нуля, есть цикл.
topoSort из урока под другим именем, только при цикле возвращается пустой список вместо null.
Каждый ингредиент указывает на рецепты, которым он нужен, запасы первыми попадают в очередь, а рецепт можно приготовить, когда его счётчик недостающих ингредиентов дошёл до нуля.
Иди в топологическом порядке и передавай множество пререквизитов каждого курса тем, кто идёт после, а потом отвечай на запросы по этим множествам.
Сделай две отдельные топологические сортировки, одну по условиям строк, другую по условиям столбцов, и поставь каждое число на его две позиции.