[洛谷 2661][NOIP2015]信息传递

题目链接

https://www.luogu.org/problem/P2661

题解

本题的任务是让我们在有向图中找一个最小环。

我们每次选一个还没有遍历的节点开始遍历。如果我们遍历到一个没有遍历过的点，记录这个点的遍历顺序，然后继续向下遍历。

如果这个节点已经被遍历，那么又分为两种情况：第一种是在这一次遍历中之前遍历的节点，在这种情况下，我们找到了一个环，这时我们可以直接与目前的最小环作比较，更新答案。

如果这个节点在以前的遍历中已经遍历过，我们就可以停止这一轮的遍历了。原因在于：无论我们遍历到的这个点是不是环上的点，都不会使答案更优。

当所有的点都被遍历时，就可以输出答案了。

显然，该算法的复杂度是 \(O(n)\) 的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t[200005],vis[200005],cyc[200005];
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&t[i]);
 int ans=200005;
 for(int i=1;i<=n;i++)
 {
  if(vis[i]==-1)continue;
  cyc[1]=i;
  vis[i]=1;
  int cnt=1,cur=i;
  while(1)
  {
   cur=t[cur];
   cyc[++cnt]=cur;
   if(vis[cur]==-1)
   {
    for(int i=1;i<=cnt;i++)
     vis[cyc[i]]=-1;
    break;
   }
   if(vis[cur]>0)
   {
    ans=min(ans,cnt-vis[cur]);
    for(int i=1;i<=cnt;i++)
     vis[cyc[i]]=-1;
    break;
   }
   vis[cur]=cnt;
  }
 }
 printf("%d\n",ans);
 return 0;
}