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

Strong Connected Components

Сильная связность

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

Задано орієнтовний граф. Зайдіть кількість різних компонент сильної зв'язності у ньому.

Вхідні дані

У першому рядку задані через пропуск два цілих числа n і m (1n10, 0m90) - кількість вершин і ребер у графі відповідно. Наступні m рядків описують ребра графа: i-ий з цих рядків містить два числа ui та vi (1ui, vin) - номери початку і кінця i-го ребра, відповідно. Гарантується, що граф не містить петель та кратних ребер.

Вихідні дані

Виведіть одне число - кількість компонент сильної зв'язності заданого графа.

prb2403.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 2
1 2
2 3
Вихідні дані #1
3
Вхідні дані #2
5 4
3 1
1 2
2 3
4 5
Вихідні дані #2
3
Джерело ЛКШ-2011 Севастополь 08.08.2011 д.2 1-я лига