题解 | #[NOIP2015]信息传递#

思路

这道题的大意就是要我们求最小环的长度。
我们知道这是一个n个顶点n条边的图，所以每一块最多只有一个环，并保证图中有环。
我们可以从任意一个点开始搜索，如果碰到了原来记录过的顶点，那么就记录答案并跳出。
如果下一个点已经被记录过了并且不是同一次搜索，那么直接跳出就好了。
这个是一个O(n)的做法。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,t[maxn],vis[maxn],dep[maxn],ans=1e7+5,cnt=0;

void dfs(int node,int k){
//    cout<<node<<" "<<k<<endl;
    if(vis[node]){
        if(vis[node]!=cnt) return;
        ans=min(ans,k-dep[node]);
        return;
    }
    dep[node]=k;
    vis[node]=cnt;
    dfs(t[node],k+1);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);
    for(int i=1;i<=n;i++){
        ++cnt; 
        if(!vis[i]) dfs(i,1);
    }
    printf("%d",ans);
    return 0;
}