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