题解 P2661 【信息传递】
panda_2134
2017-08-23 13:10:09
同样是一种基于时间戳的做法，但是和楼下的有一些不同
首先，由于每个点出度都是1，可以直接往下走而不用dfs
用一种类似于tarjan的思想：
一个子图是环，当且仅当从某个点开始走，走到的最后一个没走过的点指向的节点的时间戳，大于开始走的时候的时间戳。
然后就可以愉快的暴力了，也不需要剪枝和删点什么的
代码:
```cpp
//由于每个点出度一定为1，可以暴力找出所有的环
//对于某一个环，找到环上任意一点第一次和第二次访问的时间差即可
//而找时间差可以用时间戳完成 复杂度O(n)
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=200000,INF=0x3f3f3f3f;
int dfs_clock,N,Ans=INF,T[MAXN+10],Clk[MAXN+10];
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d",&T[i]);
for(int i=1,j;i<=N;i++)
if(!Clk[i]) {
int st=++dfs_clock;
for(j=i;!Clk[j];j=T[j])
Clk[j]=++dfs_clock;
if(Clk[j]>=st) Ans=min(Ans,dfs_clock-Clk[j]+1);
}
printf("%d",Ans);
}
```