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

1. Идея

У каждой зоны есть ровно один исходящий переход в зону p_i. Такой граф называют функциональным: из каждой вершины выходит ровно одно ребро.

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

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

Поэтому достаточно:

• соединить i и p_i как принадлежащие одной компоненте;
• посчитать количество компонент связности.

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

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

Наблюдение 1

Если из каждой вершины выходит ровно одно ребро, то при движении по переходам из любой вершины мы рано или поздно попадём в цикл.

Наблюдение 2

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

Наблюдение 3

В каждой такой компоненте цикл ровно один.

Почему?
Потому что у каждой вершины только одно исходящее ребро. Если бы в одной компоненте было два разных цикла, то для соединения их внутри одной компоненты понадобилась бы вершина, из которой можно было бы разветвиться в разные стороны, а это невозможно в функциональном графе.

Наблюдение 4

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

Именно это и делает эталонное решение: для каждой зоны i выполняется объединение i и p_i.

3. Алгоритм

1. Считываем n.
2. Создаём DSU на n вершинах.
3. Для каждой зоны i считываем p_i и объединяем множества вершин i и p_i.
4. После всех объединений считаем, сколько вершин i являются представителями своих множеств, то есть find(i) == i.
5. Это число и есть ответ.

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

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

Шаг 1. После всех объединений каждая компонента DSU совпадает с одной связной компонентой графа

Для каждой вершины есть ребро i -> p_i. Если рассматривать его как неориентированное, то вершины i и p_i должны лежать в одной компоненте.
Операция unite(i, p_i) как раз это и делает.

После обработки всех вершин DSU объединит ровно те вершины, между которыми существует путь в неориентированном смысле. Значит, множества DSU — это компоненты связности исходного функционального графа без учёта направлений.

Шаг 2. В каждой такой компоненте ровно одно транспортное кольцо

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

Шаг 3. Разные компоненты дают разные кольца

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

Итак:

• каждой компоненте связности соответствует ровно одно кольцо;
• каждому кольцу соответствует ровно одна компонента.

Следовательно, количество колец равно количеству компонент, которое и считает DSU.

5. Сложность

Пусть n — число зон.

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

С DSU с эвристиками сжатия путей и объединения по размеру суммарная сложность составляет O(n * alpha(n)), где alpha(n) — очень медленно растущая функция Аккермана. На практике это почти линейное время.

Память: O(n).

6. Код на C++17

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

struct DSU {
    vector<int> parent, sz;

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

    int find(int v) {
        while (v != parent[v]) {
            parent[v] = parent[parent[v]];
            v = parent[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);
        parent[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 p;
        cin >> p;
        dsu.unite(i, p);
    }

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

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

7. Код на Python 3

import sys


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

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

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


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n = data[0]
    p = data[1:1 + n]

    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()