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

题目链接

https://www.luogu.org/problemnew/show/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;
  memset(cyc,0,sizeof(cyc));
  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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注