第一看还以为是水题
随便打了一个bfs只有40分……
然后开始颓废
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int nxt[N];
bool vis[N];
void bfs(int x)
{
memset(vis, , sizeof(vis));
queue<int>q;
q.push(x);
vis[x] = true;
int cnt = ;
while (!q.empty())
{
int now = q.front();
if (vis[nxt[now]] == true)
{
printf("%d\n", cnt);
return;
}
else {
q.pop();
q.push(nxt[now]);
cnt++;
vis[nxt[now]] = true;
}
}
}
int main()
{
int n; scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%d", &nxt[i]);
}
for(int i=;i<=n;i++)
bfs(i);
}
垃圾代码
然后在水社区的时候
看到一个当时和我一起打这道题的网友@Frozencode （貌似是位大佬）提到这道题
一开始没怎么想写博客的
但是现在还是写吧
思路
之前是bfs，想用记忆化很难实现（我这个蒟蒻没打出来，大佬见笑了）
一开始想储存到一个点的需要的步骤储存下来
但是bfs会一直更新，不能那么草率地使用啊
然后看tag是DP?我不会DP
于是颓废的我点开了题解
题解一个是玄学模拟。我不会模拟
然后大神们很多写的Tarjan。为了试图看懂大佬的代码，我甚至想去学tarjan。但是我不会tarjan。
无奈之下，我还是回归开始的搜索，但是打dfs。
结果过了……
代码
献丑了
VS的码风
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,x,to[N],rd[N],w[N],dep[N],mk[N];
char vis[N], ins[N];
int dfs(int x);
int main()
{
scanf("%d", &n);
for (int i = ; i <= n; ++i)
scanf("%d",&to[i]),++rd[to[i]];
for (int i = ; i <= n; ++i)
if (!rd[i]) w[i] = , dfs(i);
for (int i = ; i <= n; ++i)
if (!vis[i]) dfs(i);
for (int i = ; i <= n; ++i)
printf("%d\n",w[i]);
return ;
}
int dfs(int x)
{
int t = to[x]; vis[x] = ins[x] = ;
if (!vis[t])
{
dep[t] = dep[x] + ;
w[x] = dfs(t);
w[x] += (mk[t] ? (mk[x] = (mk[x] != ? : ), ) : );
}
else
if (ins[t])
w[x] = dep[x] - dep[t] + , mk[x] = , mk[t] = (x == t ? : );
else
w[x] = w[t] + ;
ins[x] = ;
return w[x];
}
想睡觉了……因此不多解释了
现在23:11
思路也大多数是看题解的
我去找找……
找到了
这位大神的https://www.luogu.org/blog/backupnoob/solution-p2921
虽然压行可读性低，但是基本可以看懂
（说白了吧，我抄题解的……）
深深感觉到自己的弱小