A1206 [NOIP2015提高组] 信息传递

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

// 信息传递（A1206，NOIP2015 提高组）
//
// 每个人的生日沿 T 链传播：只有处在环上的人，才会收到自己的生日，
// 所以答案 = 函数图中最短环的长度。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> to(n + 1);
    for (int i = 1; i <= n; i++) cin >> to[i];

    vector<int> vis(n + 1, 0); // 0 = 没走过；否则记本次链的编号
    vector<int> pos(n + 1, 0); // 在本次链里的位置（从 1 开始）
    int id = 0;
    int ans = n + 1;

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; // 已经走过，链和环都处理过了
        id++;
        int x = i, len = 0;
        while (vis[x] == 0) {
            vis[x] = id;
            pos[x] = ++len;
            x = to[x];
        }
        // x 已被访问过：只有 vis[x] == id 时 x 才在本次链里，说明找到了环
        if (vis[x] == id) {
            ans = min(ans, len - pos[x] + 1);
        }
    }

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