Сделать граф сильно связным
1000 мс · 256 МБ · всё или ничего
Сколько рёбер надо добавить в ориентированный граф, чтобы из любой вершины стала достижима любая?
Формат ввода
В первой строке - числа и (, ).
В следующих строках - рёбра. Возможны петли и кратные рёбра.
Формат вывода
Выведите наименьшее количество рёбер, которые надо добавить.
Примеры
ввод
3 3 1 2 2 3 3 1
вывод
0
ввод
4 2 1 2 3 4
вывод
2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.