I. Длиннейшая цепочка компонент
3000 мс · 256 МБ · всё или ничего
Постройте конденсацию и найдите в ней наибольшее число компонент на одном пути.
Конденсация ациклична, а в ациклическом графе длиннейший путь считается динамикой по топологическому порядку: , где максимум берётся по рёбрам конденсации, а для стоков он равен нулю.
Отдельно сортировать конденсацию не нужно: алгоритм Косарайю нумерует компоненты в топологическом порядке, поэтому достаточно пройти по номерам от последнего к первому.
Это первая на занятии задача, где ациклическость конденсации используется по-настоящему: в исходном графе с циклами никакого длиннейшего пути не существует.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рёбрами. Возможны кратные рёбра и петли.
Формат вывода
Одно число — наибольшее количество компонент на пути.
Примеры
ввод
4 4 2 1 3 2 2 3 4 3
вывод
3
ввод
3 3 1 2 2 3 3 1
вывод
1
Войдите, чтобы отправлять решения.