Задачі
Конденсація графу
Конденсація графу
Для заданого орієнтованого графа знайти кількість ребер в його конденсації.
Конденсацією орграфа G називають такий орграф G', вершинами якого є компоненти сильної зв'язності G, а дуга в G' присутня тільки якщо існує хоча б одне ребро між вершинами, що входять у відповідні компоненти зв'язності.
Конденсація графу не містить кратних ребер.
Вхідні дані
Перший рядок містить кількість вершин n та кількість ребер m (n ≤ 104
, m ≤ 105
) графу. Кожний з наступних m рядків містить опис ребра графу. i-те ребро описується номерами початкової bi
та кінцевої ei
(1 ≤ bi
, ei
≤ n) вершини. У графі можуть бути присутні кратні ребра та петлі.
Вихідні дані
Виведіть кількість ребер в конденсації графу.
Вхідні дані #1
4 4 2 1 3 2 2 3 4 3
Вихідні дані #1
2