1. Идея

Дан массив p, где для каждой вершины i указана вершина p[i], к которой из i ведёт ребро. Нужно определить, сколько связных компонент получится, если считать эти ребра неориентированными.

Это классическая структура функционального графа: из каждой вершины выходит ровно одно ребро. В таком графе каждая связная компонента содержит ровно один цикл, а в цикл могут впадать деревья.

Значит, задача сводится к подсчёту количества связных компонент в таком графе.

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

Наблюдение 1

Если рассматривать граф как неориентированный, то вершины i и p[i] обязательно лежат в одной компоненте связности.

Значит, можно просто объединять вершины i и p[i].

Наблюдение 2

После обработки всех пар (i, p[i]) число различных множеств в структуре DSU (Disjoint Set Union, система непересекающихся множеств) и будет ответом.

Наблюдение 3

Не нужно отдельно искать циклы, запускать DFS или строить сложную логику. Достаточно сделать n объединений.

3. Алгоритм

Используем DSU.

1. Изначально каждая вершина находится в своей компоненте.
2. Для каждой вершины i:
   • читаем p[i];
   • объединяем множества, содержащие i и p[i].
3. После всех объединений считаем количество различных корней в DSU.
4. Это и есть количество связных компонент.

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

Докажем корректность.

Рассмотрим граф с вершинами 1..n, где из каждой вершины i проведено ребро к p[i]. Если забыть направление, то каждое такое ребро просто соединяет две вершины.

Структура DSU как раз умеет поддерживать разбиение вершин на компоненты связности:

• если между двумя вершинами есть ребро, то они должны быть в одной компоненте, поэтому выполняем union(i, p[i]);
• если существует путь между двумя вершинами, то после последовательных объединений всех рёбер они окажутся в одном множестве;
• если пути нет, то никакая последовательность объединений не соединит их.

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

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

5. Сложность

Пусть n — число вершин.

• Выполняется n операций объединения.
• Каждая операция find и union работает за O(α(n)), где α — обратная функция Аккермана, которая на практике очень мала.

Итоговая сложность:

• по времени: O(n α(n))
• по памяти: O(n)

CPP

#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);
        iota(p.begin(), p.end(), 0);
    }

    int find(int v) {
        if (p[v] == v) return v;
        return p[v] = find(p[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 ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (dsu.find(i) == i) ++ans;
    }

    cout << ans << '\n';
    return 0;
}

PYTHON

import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    p = list(map(int, input().split()))

    parent = list(range(n + 1))
    size = [1] * (n + 1)

    def find(v):
        while parent[v] != v:
            parent[v] = parent[parent[v]]
            v = parent[v]
        return v

    def unite(a, b):
        a = find(a)
        b = find(b)
        if a == b:
            return
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    for i in range(1, n + 1):
        unite(i, p[i - 1])

    ans = 0
    for i in range(1, n + 1):
        if find(i) == i:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()