每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。
由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。
FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。
在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。
第1行 整数n。
第2行到n+1行 每行包含一个整数 。
n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。
第一次写蓝题题解好激动啊哈哈哈哈……
发现很多人都是用Tarjan或者记忆搜索，我就蛮奇怪
不是说不能用tarjan，而是这题完全没有必要哈，，，
get网上志同道合的一个OIer的讲解：
首先我们需要注意到一点，虽然此题也是一张有向图，但是每个点的出度有且只有 “1”。这说明什么？不需要递归，直接沿着这条唯一的路径走下去就行了…
一、为了实现这一方法，我们对每个点设置两个属性：
1、颜色 (color)： 此节点第一次被访问时，这条访问他的路径是由那个节点发出的（起点）。
2、时间戳 (dfn) ：此节点第一次被访问时，他到发出这条路径的起点的距离（发出节点的 dfn=0，第二个被访问的节点的 dfn = 1,第三个 dfn = 2 …）
有了这两个属性，我们就可以计算环的大小，方法如下：
1、从某一节点发出路径
2、走到某个节点上（包括起点），如果这个节点没有被染色，那么染成自己的颜色，并标记上 dfn
3、走到某个节点上，如果这个节点已经被染成了自己的颜色，那么环的大小就出来了：当前时(cnt) − 此节点 dfn
到了这一步，实际上已经解决了另一个更简单的问题：NOIP2015 信息传递。 接下来就是本题特色了
二、对于每一只奶牛（或者说每一个起点、颜色、路径），我们记录如下两个属性：
1、环的大小 (minc)：每条路径最终都会进入环中，或者起点本身就在环中，我们记录下这个环的大小为之后服务
2、入环时间戳 (sucdfn) ：这条路径什么时候会进入环中，同样是为之后服务的一个属性
首先讲解一下如果得到这两个属性：
1、在上一节中我们已经讲了如何初步获取环的大小，入环时间戳只要记录为那个交点的时间戳即可
2、如果走到了之前走过的节点，那么新的路径必然进入之前路径的环中，直接把这个环的大小要过来就行了。入环时间戳则分两种情况：
i. 如果这个节点不在环中，“原路径的入环时间戳 -− 原路径中此节点的时间戳 + 新路径当前时间” 即为新路径的入环时间戳;
ii. 而如果这个节点在环中，直接就是新路径当前时间。
iii. 判断方法则是 “原路径的入环时间戳 - 原路径中此节点的时间戳” 是否大于 0，综合起来就是：“
三、把上面的问题都解决了，出答案就太简单了：
1、第一节中的发现环的大小之后，答案就是“当前时间”
2、第二节中与之间走过的节点相遇并记录完信息后，答案是 “入环时间戳 + 环的大小”
至此本题已经完美解决，且没有用到任何算法。贴代码：
我要评论#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
int n;
int nxt[maxn];
int color[maxn];
int sucdfn[maxn];
int dfn[maxn];
int minc[maxn];
void Init()
{
cin >> n;
for(int i = 1; i <= n; ++i) cin >> nxt[i];
memset(color, 0, sizeof(color));
memset(dfn, 0, sizeof(dfn));
memset(minc, 0, sizeof(minc));
}
void Solve()
{
for(int cow = 1; cow <= n; ++cow)
{
for(int i = cow, cnt = 0; ; i = nxt[i], ++cnt)
{
if(!color[i]) {
color[i] = cow;
dfn[i] = cnt;
}
else if(color[i] == cow) {
minc[cow] = cnt - dfn[i];
sucdfn[cow] = dfn[i];
cout << cnt << endl;
break;
}
else {
minc[cow] = minc[color[i]];
sucdfn[cow] = cnt + max(sucdfn[color[i]] - dfn[i], 0);
cout << sucdfn[cow] + minc[cow] << endl;
break;
}
}
}
}
int main()
{
Init();
Solve();
return 0;
}
还有你们要的最短代码：
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,to[N],rd[N],w[N],dep[N],mk[N];char vis[N],ins[N];
int dfs(int x){
int t=to[x];vis[x]=ins[x]=1;
if(!vis[t]){dep[t]=dep[x]+1;w[x]=dfs(t);w[x]+=(mk[t]?(mk[x]=(mk[x]!=2?1:0),0):1);}
else if(ins[t])w[x]=dep[x]-dep[t]+1,mk[x]=1,mk[t]=(x==t?0:2);
else w[x]=w[t]+1;
ins[x]=0;return w[x];
}
int main(){
ios::sync_with_stdio(false);cin>>n;int x;
for(int i=1;i<=n;++i)cin>>to[i],++rd[to[i]];
for(int i=1;i<=n;++i)if(!rd[i])w[i]=1,dfs(i);
for(int i=1;i<=n;++i)if(!vis[i])dfs(i);//totally a cycle
for(int i=1;i<=n;++i)cout<<w[i]<<endl;
return 0;
}
本文地址：https://blog.csdn.net/qq_42040281/article/details/85976119
如对本文有疑问， 点击进行留言回复！！
现在微服务这么火，你还不了解吗？阿里P8推荐的微服务学习指南
论文笔记：SlowFast Networks for Video Recognition
网友评论