Задачи
Конденсация графа
Конденсация графа
Для заданного ориентированного графа найти количество ребер в его конденсации.
Конденсацией орграфа G называют такой орграф G', вершинами которого служат компоненты сильной связности G, а дуга в G' присутствует только если существует хотя бы одно ребро между вершинами, входящими в соответствующие компоненты связности.
Конденсация графа не содержит кратных ребер.
Входные данные
Первая строка содержит количество вершин n и количество ребер m (n ≤ 10^4
*, m ≤ 10^5
) графа. Каждая из следующих m строк содержит описание ребра графа. i-ое ребро описывается номерами начальной b[i]
и конечной e[i]
(1 ≤ b[i]
, e[i]
≤ n) вершины. В графе могут присутствовать кратные ребра и петли.
Выходные данные
Выведите количество ребер в конденсации графа.
Пример
Входные данные #1
4 4 2 1 3 2 2 3 4 3
Выходные данные #1
2