【第12题】[NOIP2015 提高组] 信息传递

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

struct edge {
    int r, h;
};

struct UF {
    vector<edge> fa;
    vector<int> m;

    UF(int n) :
            fa(n + 1), m(n + 1) {}

    void initialize (int n) {
        for (int i = 1; i <= n; ++i) {
            cin >> m[i];
            fa[i].r = i;
        }
    }

    int Find(int a) {
        if (a != fa[a].r) {
            int r = fa[a].r;
            fa[a].r = Find(fa[a].r);
            fa[a].h += fa[r].h;
        }
        return fa[a].r;
    }

    void Union(int x, int y, int &ans) {
        int b = Find(y);
        int a = Find(x);
        if (a != b) {
            fa[a].r = b;
            fa[x].h = fa[y].h + 1;
        } else {
            ans = min(ans, fa[x].h + fa[y].h + 1);
        }
    }
};

void best_coder() {
    int n;
    cin >> n;
    UF uf(n);
    uf.initialize(n);
    int ans = 0x7f7f7f7f;
    for (int i = 1; i <= n; ++i) {
       uf.Union(i, uf.m[i], ans);
    }

    cout << ans;
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 返回
    return 0;
}