思路与算法

每人唯一出边形成函数图，信息第一次返回本人恰是最短有向环长度。Kahn剥除入度0点，剩余点逐环计数取最小。

正确性说明

一条生日信息沿唯一出边每轮前进一步，回到来源须绕某个包含来源的有向环，所以最早回传为最短环。入度0点不在环上，反复删除仍只删树枝；最后剩余部分恰为互不相交的环，计长取小即答案。

复杂度

O(n)时间、O(n)空间；含入度、队列与访问标记初始化，每点每边至多常数次处理。

易错点

输入排除自传生日，最短环至少2；不能把最长入树链长度当成结束轮数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> to(n), in(n), q;
    for (int &x : to) {
        cin >> x;
        --x;
        in[x]++;
    }
    for (int i = 0; i < n; i++)
        if (!in[i])
            q.push_back(i);
    for (int i = 0; i < (int)q.size(); i++)
        if (!--in[to[q[i]]])
            q.push_back(to[q[i]]);
    int ans = n;
    for (int i = 0; i < n; i++)
        if (in[i]) {
            int v = i, c = 0;
            do {
                in[v] = 0;
                c++;
                v = to[v];
            } while (v != i);
            ans = min(ans, c);
        }
    cout << ans << "\n";
}