这样只有80分
by aface0427 @ 2017-07-23 16:30:05
不不不，我怎么被头像吸引进来了（光速逃
by morainzh @ 2017-07-23 17:33:17
这是我的程序，123ms，我觉得还是挺快的，用了个类似并查集（其实就记一个集合即可）的方法，来简单说明一下。
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int n,num,t[200005],f[200005],d[200005],ans=2147483647;
int dfs(int x,int dep){
if (f[x]==num) return dep-d[x];
if (f[x]) return 2147483647;
f[x]=num;
d[x]=dep;
return dfs(t[x],dep+1);
}
int main(){
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d",&t[i]);
for (int i=1; i<=n; i++) if (!f[i]) ans=min(ans,dfs(i,++num));
printf("%d",ans);
}
```
\* 其实也不难，题目就像你说的，找出最小环即可。
\* 可是如果正常的dfs，像你那个那样，就会有许多重复的枚举。
\* 想象个极限数据，一个大环，然后环上每个点都向外连着一个单独的点，这样这个环会被重复弄好多遍。
\* 注意题目中每个点出度为 1，也就是说每个点只能在一个环中，且每个联通块中最多就一个环。
\* 你弄个 `f` 数组记一下每个点第一次是在第几个 dfs 中搜到的，（第几个就开个变量 num，每次新建一个搜索时累加）然后在 dfs 中若遇到当前点 `f` 就为当前的 dfs 组，那么就说明得到了一个环，要是当前点的 `f` 值非空但不为当前的 dfs 组，说明这一次 dfs 的点所在的联通块中的环已经讨论过了，就不用再往下搜了。
\* 这样时间保证在了 O(n) ，是不是很快呢~
by piggy @ 2017-07-27 01:14:38
请记录，这个点在被访问过吗，最后访问的起点
by username_invalid @ 2017-08-13 22:08:21
用tarjan搞啊
by DYT_ @ 2017-08-15 16:05:50