L. Авиалинии
3000 мс · 256 МБ · всё или ничего
Дан ориентированный граф рейсов. Составьте новый план с наименьшим числом рейсов так, чтобы достижимость между городами не изменилась: если из можно было долететь до (возможно, с пересадками), то и в новом плане можно, и наоборот. Новые рейсы разрешено проводить между любыми парами городов.
Выведите только количество рейсов в наименьшем плане.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рейсами. Возможны кратные рейсы; петель нет.
Формат вывода
Одно число — наименьшее возможное количество рейсов.
Примеры
ввод
4 5 1 2 2 3 2 1 3 2 2 4
вывод
4
ввод
3 3 1 2 2 3 1 3
вывод
2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.