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

Strong Connected Components

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

Назовём компонентой сильной связности в ориентированном графе произвольное множество вершин такое, что из любой вершины этого множества существует путь в любую другую вершину этого множества, и не существует другого множества с аналогичным свойством, содержащего это множество.

Дан ориентированный граф. Найдите количество различных компонент сильной связности в нём.

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

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

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

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

Лимит времени 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-я лига