萌新刚学tarjan,求助一步的正确性
  • 板块学术版
  • 楼主Mophie
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/3/15 20:40
  • 上次更新2023/11/5 02:01:00
查看原帖
萌新刚学tarjan,求助一步的正确性
97304
Mophie楼主2021/3/15 20:40

萌新刚学 tarjan\texttt{tarjan},有一步不是很懂。

for(int i=0;i<G[x].size();i++)
    {
        int q=G[x][i];
        if (!dfn[q])
        {
            tarjan(q);
            low[x]=min(low[x],low[q]);
        }
        else if (vis[q]) low[x]=min(low[x],dfn[q]);
    }

为什么第一次要 low[x]=min(low[x],low[q])low[x]=min(low[x],low[q]),第二次要 low[x]=min(low[x],dfn[q])low[x]=min(low[x],dfn[q]) 啊?

教练说是要避免横岔边而影响答案,但还不是很懂。

有没有神仙给个 Hack 数据或者详细解释啊/ll

2021/3/15 20:40
加载中...