1. Идея

Каждая поляна i соединена тропой с поляной a[i]. По условию нас интересует не направление связи, а только факт соединения: можно считать, что между i и a[i] есть обычное неориентированное ребро.

Тогда задача сводится к подсчёту числа связных компонент в графе из n вершин, где для каждой вершины i есть ребро i - a[i].

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

• находить, в какой компоненте находится вершина;
• объединять две компоненты.

Будем последовательно объединять вершины i и a[i], а затем посчитаем, сколько различных компонент получилось.

2. Наблюдения

1. У каждой вершины есть ровно одна исходящая связь, но для связности это неважно: направление игнорируется.

2. Если a[i] = i, то это просто петля на самой вершине. Она не соединяет её с другими вершинами и не меняет число компонент.

3. После обработки всех пар i, a[i] две вершины окажутся в одной компоненте тогда и только тогда, когда между ними есть путь в неориентированном смысле.

4. DSU идеально подходит для задачи, потому что каждое ребро просто объединяет две вершины.

3. Алгоритм

1. Считываем n.
2. Создаём DSU на n вершинах.
3. Для каждого i от 1 до n:
   • считываем x = a[i];
   • выполняем unite(i, x).
4. После этого считаем количество корней:
   • для каждого i от 1 до n проверяем, является ли i представителем своей компоненты, то есть find(i) == i;
   • если да, увеличиваем ответ.
5. Выводим количество компонент.

4. Почему это работает

Докажем, что алгоритм действительно находит число духовных кругов.

Каждая связь i -> a[i] по условию рассматривается как обычная неориентированная связь между полянами i и a[i]. Значит, если в графе есть ребро между двумя вершинами, они должны принадлежать одной и той же связной компоненте.

Именно это делает операция unite(i, a[i]): она помещает вершины i и a[i] в одно множество DSU.

После обработки всех вершин выполнены объединения для всех рёбер графа. Следовательно:

• если две вершины соединены путём, то по рёбрам этого пути их множества будут последовательно объединены, и в итоге они окажутся в одной компоненте DSU;
• если две вершины не соединены никаким путём, то ни одна последовательность объединений не сможет сделать их элементами одной компоненты.

Значит, множества DSU после всех операций в точности совпадают со связными компонентами графа.

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

5. Сложность

Пусть n — количество полян.

• Выполняется n операций объединения.
• Затем выполняется n операций поиска для подсчёта компонент.

С учётом сжатия путей и объединения по размеру, каждая операция работает практически за константу.

Итоговая сложность: O(n * alpha(n)), где alpha — обратная функция Аккермана, очень медленно растущая.

По памяти: O(n).

6. Код на C++17

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;

    DSU(int n) {
        p.resize(n + 1);
        sz.assign(n + 1, 1);
        for (int i = 1; i <= n; ++i) p[i] = i;
    }

    int find(int v) {
        while (v != p[v]) {
            p[v] = p[p[v]];
            v = p[v];
        }
        return v;
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    DSU dsu(n);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        dsu.unite(i, x);
    }

    int components = 0;
    for (int i = 1; i <= n; ++i) {
        if (dsu.find(i) == i) ++components;
    }

    cout << components - 1 << '\n';
    return 0;
}

7. Код на Python 3

import sys

class DSU:
    def __init__(self, n):
        self.p = list(range(n + 1))
        self.sz = [1] * (n + 1)

    def find(self, v):
        while v != self.p[v]:
            self.p[v] = self.p[self.p[v]]
            v = self.p[v]
        return v

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.p[b] = a
        self.sz[a] += self.sz[b]

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    p = data[1:1 + n]

    dsu = DSU(n)
    for i, x in enumerate(p, 1):
        dsu.unite(i, x)

    components = 0
    for i in range(1, n + 1):
        if dsu.find(i) == i:
            components += 1

    print(components - 1)

if __name__ == "__main__":
    main()