e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Strong Connected Components

Конденсация графа

Для заданного ориентированного графа найти количество ребер в его конденсации.

Конденсацией орграфа G называют такой орграф G', вершинами которого служат компоненты сильной связности G, а дуга в G' присутствует только если существует хотя бы одно ребро между вершинами, входящими в соответствующие компоненты связности.

Конденсация графа не содержит кратных ребер.

Входные данные

Первая строка содержит количество вершин n и количество ребер m (n10000, m100000) графа. Каждая из следующих m строк содержит описание ребра графа. i-ое ребро описывается номерами начальной bi и конечной ei (1bi, ein) вершины. В графе могут присутствовать кратные ребра и петли.

Выходные данные

Выведите количество ребер в конденсации графа.

prb1947.gif

Лимит времени 1 секунды
Лимит использования памяти 256 MiB
Входные данные #1
4 4
2 1
3 2
2 3
4 3
Выходные данные #1
2
Автор Виталий Гольдштейн
Источник Зимняя школа, Харьков 2011, День 9