10355: Конденсація графа-1


Відправити розв'язок

Бали: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js

Заданий орієнтований граф. Знайдіть кількість ребер в його конденсації.
Примітка: конденсація не містить кратних ребер.

Формат вхідних даних

Перший рядок містить два цілих числа \(N,M\) - кількість вершин та кількість ребер. (\(1 \le N \le 20000 , 1 \le M \le 200000\)).
Кожен з наступних \(M\) рядків містить по два числа \(V1,V2\) - номера початкової та кінцевої вершини кожного ребра

Формат вихідних даних

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

Приклад вхідних даних

4 4
2 1
3 2
2 3
4 3

Приклад вихідних даних

2

Пояснення до прикладу

Граф містить 3 сильнозв'язні компоненти: 1) вершина 4 2) вершини 2 та 3 3) вершина 1

Якщо побудувати конденсацію графа, то будуть присутні ребра між компонентами 1 та 2, і компонентами 2 та 3


Коментарі

Ще немає коментарів.