Minimal version selection как в Go modules
Условие
Реализуйте выбор версий зависимостей Go (MVS). Дан граф требований: узел это модуль@версия, рёбра это его require. Корень main.
Алгоритм: обойдите все узлы, достижимые из main по рёбрам (включая требования тех версий, которые в итоге не будут выбраны). Для каждого модуля выберите максимальную версию среди достигнутых.
Версии имеют вид vX.Y.Z, сравниваются численно.
Ввод: k (1 ≤ k ≤ 1000), затем k строк вида узел: требование требование ... (у main узел записан как main). Узлы, для которых строки нет, требований не имеют. Строки идут в произвольном порядке.
Вывод: итоговый список сборки без main: строки модуль версия, отсортированные по имени модуля. Если зависимостей нет, ничего не выводите.
Пример
3
main: a@v1.2.0 b@v1.0.0
a@v1.2.0: c@v1.3.0
b@v1.0.0: c@v1.4.0 a@v1.1.0
a v1.2.0
b v1.0.0
c v1.4.0
Как подойти
Обход графа из main с visited, для каждого модуля максимум версии, сортировка имён.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.