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

Strong Connected Components

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

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

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

Конденсація графу не містить кратних ребер.

Вхідні дані

Перший рядок містить кількість вершин n та кількість ребер m (n104, m105) графу. Кожний з наступних m рядків містить опис ребра графу. i-те ребро описується номерами початкової bi та кінцевої ei (1bi, ein) вершини. У графі можуть бути присутні кратні ребра та петлі.

Вихідні дані

Виведіть кількість ребер в конденсації графу.

prb1947.gif

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