Изменения
Нет описания правки
# Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний на чашечных весах: по одной гирьке на каждой чаше. Известны результаты этих взвешиваний. Определите какой-нибудь порядок гирек, который не противоречит результатам взвешивания за $O(n + m)$.
# Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний по порядку на чашечных весах: по одной гирьке на каждой чаше. Известны возможные результаты этих взвешиваний, возможно, некоторые из них некорректные. Определите, после какого из взвешиваний, полученная информация стала противоречивой за $O((n + m) \log n)$.
# У вас есть $n$ дел, а также некоторые дела зависят от других: их нельзя сделать раньше тех, от которых зависят. Граф зависимостей дел не имеет циклов. Каждое дело занимает у вас один час. Известно дело под номером $x$, которое является очень важным. Определите порядок выполнения всех дел, чтобы то, которое под номером $x$, было выполнено как можно раньше , за линейное от размера входных данных время.
# Предложите алгоритм, который находит лексикографически минимальную топологическую сортировку за $O((V + E) \log V)$.
# Предложите алгоритм, который находит топологическую сортировку, у которой обратная перестановка минимальна лексикографически за $O((E + V) \log V)$.
# Предложите алгоритм, который проверяет, что в ориентированном графе для любой пары вершин $(v, u)$ существует как путь из $v$ в $u$, так и путь из $u$ в $v$, за $O(E + V)$.
# Задан ориентированный граф, у каждой вершины исходящая степень равна 1. У каждого ребра есть вес. Вы забыли про ориентацию ребер, найдите паросочетание максимального веса за $O(E + V)$.
# Предложите алгоритм, который добавляет в ацикличный ориентированный граф ровно одно ребро, чтобы он остался ацикличным, так, чтобы максимальный по длине путь был как можно длиннее за $O(V^2 + E + V)$.
</wikitex>
