题解 P2661 【信息传递】

2017-08-23 13:10:09


同样是一种基于时间戳的做法,但是和楼下的有一些不同

首先,由于每个点出度都是1,可以直接往下走而不用dfs

用一种类似于tarjan的思想:

一个子图是环,当且仅当从某个点开始走,走到的最后一个没走过的点指向的节点的时间戳,大于开始走的时候的时间戳。

然后就可以愉快的暴力了,也不需要剪枝和删点什么的

代码:

//由于每个点出度一定为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);
}