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