11. Свинки-копилки

Задача

Васе нужно открыть все копилки, располагая только ключами, находящимися внутри некоторых из них. Определите минимальное количество копилок, которые придётся разбить.

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

В первой строке содержится число $n$ ($1 \leqslant n \leqslant 100$) — количество свинок-копилок. Далее следует $n$ строк: в $i$-й строке указана копилка, в которой лежит ключ от $i$-й копилки.

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

Выведите минимальное количество копилок, которые необходимо разбить, чтобы получить доступ ко всем ключам.

Пример

стандартный ввод      стандартный вывод
4                      2
2
1
2
4

Ограничения

  • Время: 1 секунда
  • Память: 256 мегабайт
Редакционный разбор Каждой копилке соответствует вершина графа, из которой выходит ровно одно ребро — к копилке, где лежит её ключ. Это ориентированный граф, состоящий из циклов с деревьями, которые в них впадают (функциональный граф). Открывать копилки можно по цепочке: разбиваем любую копилку цикла, достаём ключи и дальше открываем остальные по ребрам, не разрушая их. Значит, достаточно разбить по одной копилке в каждом цикле. Ответ равен количеству циклов в функциональном графе. Чтобы посчитать их, отмечаем посещённые вершины и запоминаем состояние (`0` — не посещена, `1` — в стеке, `2` — обработана). При попадании в вершину со статусом `1` обнаруживаем новый цикл и увеличиваем ответ. Сложность $O(n)$.

Mentioned by