Кольца большого мегаполиса

Просмотр в формате PDF

Submit solution


Очки: 140
Ограничение по времени: 1.0s
Ограничение по памяти: 64M

Автор:
Problem types
Allowed languages
C++, Python

В футуристическом мегаполисе действует n транспортных зон, пронумерованных от 1 до n.

Из каждой зоны автоматическая система перенаправления отправляет пассажира ровно в одну зону. Для каждой зоны i известно число p_i — номер зоны, в которую ведёт перенаправление из зоны i.

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

Требуется определить, сколько различных транспортных колец существует в мегаполисе.

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

В первой строке содержится одно целое число n — количество транспортных зон.

Во второй строке содержатся n целых чисел p_1, p_2, ..., p_n, где p_i — зона, в которую ведёт перенаправление из зоны i.

Ввод осуществляется через стандартный ввод.

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

Выведите одно целое число — количество транспортных колец.

Вывод осуществляется через стандартный вывод.

Ограничения

  • 1 <= n <= 200000
  • 1 <= p_i <= n

Примеры

Пример 1

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

8
1 2 3 4 5 6 7 8

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

8
Пример 2

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

11
2 1 4 3 6 5 8 7 10 9 11

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

6

Комментарии

Еще нет ни одного комментария.