思路1： 可以把它看成一个n个点，n条边的图，问题转换为求一个最小环。由于只有n条边，求环等价于求结点数大于2的强连通分量。然后用Kosaraju算法写（不要问我为什么不用Tarjan= =）：
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <map> #include <set> using std::cin; using std::cout; using std::endl; inline int readIn() { int a; scanf("%d", &a); return a; } const int maxn = 200005; int n; int G[maxn]; bool vis[maxn]; std::vector<std::vector<int> > GT; std::stack<int> sequeue; int ans = -1; int temp; void dfsG(int from) { if(vis[from]) return; vis[from] = true; dfsG(G[from]); sequeue.push(from); } void dfsGT(int from) { if(vis[from]) return; vis[from] = true; temp++; for(int i = 0; i < GT[from].size(); i++) { dfsGT(GT[from][i]); } } void run() { n = readIn(); GT.resize(n + 1); for(int i = 1; i <= n; i++) { G[i] = readIn(); GT[G[i]].push_back(i); } memset(vis, 0, sizeof(bool) * (n + 1)); for(int i = 1; i <= n; i++) { if(!vis[i]) dfsG(i); } memset(vis, 0, sizeof(bool) * (n + 1)); while(!sequeue.empty()) { int top = sequeue.top(); sequeue.pop(); if(vis[top]) continue; temp = 0; dfsGT(top); if(temp > 1 && (ans == -1 || temp < ans)) { ans = temp; } } printf("%d\n", ans); } int main() { run(); return 0; }这代码看上去一切正常对不对！可惜，在n=200000时，dfs不幸爆栈了。。。 预计得分：100 实际得分：90
思路2：其实这道题直接”dfs“的时候判断有没有重复经过点就好了，走的时候再记录一下步数。由于每个点只有一个出度，所以用循环模拟dfs，防止了爆栈的发生。
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <string> #include <stack> #include <queue> #include <deque> #include <map> #include <set> using std::cin; using std::cout; using std::endl; inline int readIn() { int a; scanf("%d", &a); return a; } const int maxn = 200005; int n; int G[maxn]; bool vis[maxn]; int step[maxn]; int Index[maxn]; //只有当index相等时才能说明是在同一次搜索中搜到的，这时才能判断是不是找到了圈 //若index不相等，则只是相当于重复访问了结点，应及时退出 int count_; int ans = -1; void dfs(int from) { step[from] = 1; while(true) { vis[from] = true; Index[from] = count_; if(vis[G[from]] && step[G[from]] && Index[G[from]] == count_) //找到圈 { if(step[from] - step[G[from]] + 1 > 1 && (ans == -1 || ans > step[from] - step[G[from]] + 1)) { ans = step[from] - step[G[from]] + 1; } return; } else if(vis[G[from]]) return; else { step[G[from]] = step[from] + 1; from = G[from]; } } } void run() { n = readIn(); for(int i = 1; i <= n; i++) { G[i] = readIn(); } for(int i = 1; i <= n; i++) { if(!vis[i]) { count_++; dfs(i); } } printf("%d\n", ans); } int main() { run(); return 0; }其中，还是要十分注意里面的细节，比如那个Index数组的使用和step数组的使用。想清楚再写，不然很容易写错。前9组数据还是有点弱，哪怕代码有点瑕疵都能过，但是第10组数据很强= =。
