关于tarjan的一些小问题
查看原帖
关于tarjan的一些小问题
251449
hfjh楼主2023/3/27 08:50

核心代码中low代表的是

low[i]是从i点出发,所能访问到的最早的进入时间

这句代码有点不懂

low[x]=min(low[x],dfn[edge[i].to]);

low[x]代表x可以访问到的最早进入时间

x可以访问到y,y可以访问的最早进入时间是low[y]

所以为什么不是

low[x]=min(low[x],low[edge[i].to]);

(虽然两种都可以过,但是大家一般都写的上面这种不懂为什么

	for(int i=heads[x];i!=-1;i=edge[i].next)
    {
        if(!dfn[edge[i].to])
        {
           	tarjan(edge[i].to);
            low[x]=min(low[x],low[edge[i].to]);
       	}
       	else 
        if(visit[edge[i].to])
        low[x]=min(low[x],dfn[edge[i].to]);
    }
2023/3/27 08:50
加载中...