Изменения
Нет описания правки
# Задан ориентированный граф, у каждой вершины исходящая степень равна 1. У каждого ребра есть вес. Вы забыли про ориентацию ребер, найдите паросочетание максимального веса за $O(E + V)$.
# Предложите алгоритм, который добавляет в ацикличный ориентированный граф ровно одно ребро, чтобы он остался ацикличным, так, чтобы максимальный по длине путь был как можно длиннее за $O(V^2 + E)$.
# Задан ориентированный граф. В вершинах записаны числа от 1 до $|V|$, все различные. Профилем вершины назовем следующую последовательность: возьмем все вершины достижимые из нее, все числа записанные на этих вершинах и упорядочим. Отсортируйте вершины по профилю лексикографически за $O(E + V)$.
# Задан ацикличный ориентированный граф. Удалите в нем одно ребро, чтобы число простых путей в графе стало как можно меньше за $O(E + V)$.
# Задан ориентированный граф, в каждой вершине записано число. Для каждой вершины $v$ найдите $f(v)$ {{---}} вершину с максимальным числом, которая достижима из $v$, за $O(E + V)$.
