思路
显然，所有的边都是有向边。那么一个人能够得到自己的生日的条件便是这个人在一个环中，而且要求的是最小环。那么我们就可以用Tarjan算法求解。不会Tarjan的人可以去看看我另一篇随笔，专门讲的Tarjan我脚地窝写的海星。想看的话可以点这里。还有就是要注意环的大小必须要超过1。。。。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
const int maxn = 2e5+3;
using namespace std;
stack<int> S;
int n, x, f, u[maxn], v[maxn], first[maxn], next[maxn], cnt;
char c;
bool vis[maxn];
int low[maxn], dfn[maxn], Index, tot, ans = 2147483647;
inline int readInt() {
x = 0, f = 1;
c = getchar();
while (c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while (c <= '9' && c >= '0') {
x = x*10 + c-'0';
c = getchar();
}
return x * f;
}
inline void Tarjan(int now) {
low[now] = dfn[now] = ++Index;
S.push(now);
vis[now] = 1;
int k = first[now];
while (k != -1) {
if(!dfn[v[k]]) {
Tarjan(v[k]);
low[now] = min(low[now], low[v[k]]);
}
else if(vis[v[k]] && dfn[v[k]]) {
low[now] = min(low[now], dfn[v[k]]);
}
k = next[k];
}
int temp, num = 0;
if(dfn[now] == low[now]) {
while(!S.empty()) {
temp = S.top();
S.pop();
num ++;
vis[temp] = 0;
if(temp == now) break;
}
if(num > 1) {
ans = min(ans, num);
}
}
}
int main() {
n = readInt();
memset(first, -1, sizeof(first));
for(int i=1; i<=n; i++) {
u[i] = i, v[i] = readInt();
next[i] = first[u[i]];
first[u[i]] = i;
}
for(int i=1; i<=n; i++) {
if(!dfn[i]) Tarjan(i);
}
printf("%d", ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9334307.html
相关资源：数据结构—成绩单生成器
