1. Идея

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

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

Главная идея задачи очень простая:

• если не учитывать направления, то каждая связная компонента такого графа уже связна;
• внутри каждой такой компоненты обязательно есть хотя бы один цикл;
• чтобы сделать весь граф связным, достаточно соединить его компоненты между собой;
• если компонент k, то минимально нужно добавить k - 1 ребро.

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

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

Наблюдение 1. Граф состоит из компонент, в каждой из которых есть цикл

Так как из каждой вершины выходит ровно одно ребро, если идти по рёбрам из любой вершины, то рано или поздно мы попадём в уже посещённую вершину. Значит, образуется цикл.

То есть каждая компонента функционального графа выглядит так:

• один цикл;
• в его вершины могут входить деревья.

Например:

• 1 -> 2 -> 3 -> 1 — цикл;
• 4 -> 2, 5 -> 4 — вершины, которые «подвешены» к циклу.

Наблюдение 2. Если убрать направления, каждая такая часть остаётся одной компонентой

По условию у каждой вершины есть связь с p[i]. Если рассматривать это как неориентированное ребро между i и p[i], то все вершины, ведущие в один и тот же цикл, лежат в одной компоненте связности.

Значит, количество нужных добавлений зависит только от числа таких компонент.

Наблюдение 3. Минимум добавленных рёбер для соединения k компонент равен k - 1

Это общее свойство графов:

• одним ребром можно уменьшить число компонент не более чем на 1;
• чтобы из k компонент сделать одну, нужно хотя бы k - 1 ребро;
• этого всегда можно добиться, просто соединяя компоненты в цепочку.

Итак, ответ равен:

число компонент - 1

3. Алгоритм

Будем искать компоненты связности.

Удобно использовать DSU (система непересекающихся множеств, union-find).

Шаги

1. Считать n.
2. Для каждой вершины i считать p[i].
3. Объединить в DSU вершины i и p[i].
4. После всех объединений посчитать количество различных корней в DSU.
5. Ответ: components - 1.

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

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

Шаг 1. После объединения всех пар (i, p[i]) множества DSU совпадают с компонентами связности неориентированного графа

Мы добавляем ребро между i и p[i] для каждой вершины.
DSU как раз и объединяет вершины, соединённые путём по таким рёбрам.

Значит:

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

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

Шаг 2. Чтобы сделать весь граф связным, нужно не меньше components - 1 рёбер

Изначально есть components компонент. Одно новое ребро может соединить максимум две разные компоненты, то есть уменьшить их число не более чем на 1.

Чтобы из components компонент получить одну, необходимо как минимум:

components - 1

рёбер.

Шаг 3. components - 1 рёбер всегда достаточно

Выберем по одной вершине из каждой компоненты и соединим компоненты в цепочку:

• 1-ю со 2-й,
• 2-ю с 3-й,
• ...
• (components-1)-ю с components-й.

Будет добавлено ровно components - 1 ребро, и все компоненты станут одной.

Из шагов 2 и 3 следует, что минимальное число добавленных рёбер равно components - 1.

Следовательно, алгоритм верно находит ответ.

5. Сложность

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

DSU

Для каждой вершины выполняется одно объединение.
С амортизированной оптимизацией (path compression + union by size/rank) все операции работают за почти константное время.

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

• по времени: O(n α(n)), что на практике почти O(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

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

    def find(self, v):
        while self.p[v] != 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:]

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

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

    print(ans)

if __name__ == "__main__":
    main()