Изменения
Нет описания правки
# Задан ориентированный граф улиц в городе. Нужно поставить полицейские станции в вершинах. Всего нужно поставить ровно $k$ станций так, чтобы из каждой вершины была достижима хотя бы одна станция и каждая вершина была достижима из хотя бы одной станции. Выведите число способов поставить $k$ станций в $k$ различных вершин за $O(E + V)$.
# Задан неориентированный граф, степень каждой вершины не больше двух. Найдите минимальное вершинное покрытие в графе за $O(E + V)$.
# Задан несильносвязный турнир. Турнир {{---}} ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $O(V^2)$.
</wikitex>
