Изменения

# Задан ориентированный граф, у каждой вершины исходящая степень равна 1. У каждого ребра есть вес. Вы забыли про ориентацию ребер, найдите паросочетание максимального веса за $O(E + V)$.

# Предложите алгоритм, который добавляет в ацикличный ориентированный граф ровно одно ребро, чтобы он остался ацикличным, так, чтобы максимальный по длине путь был как можно длиннее за $O(V^2 + E)$.

# Задан ориентированный граф, в каждой вершине записано число. Для каждой вершины $v$ найдите $f(v)$ {{---}} вершину с максимальным числом, которая достижима из $v$, за $O(E + V)$.

# Задан неориентированный граф. Покрасьте граф в два цвета, чтобы число вершин первого цвета было равно числу вершин второго цвета за $O(V^2+E)$.

# Задан неориентированный граф, степень каждой вершины не больше двух. Найдите минимальное вершинное покрытие в графе за $O(E + V)$.

# Задан несильносвязный турнир. Турнир {{---}} ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $O(V^2)$.

</wikitex>