关于 Tarjan 算法
  • 板块学术版
  • 楼主lmjsjg
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/26 21:50
  • 上次更新2023/10/27 05:43:02
查看原帖
关于 Tarjan 算法
513009
lmjsjg楼主2022/10/26 21:50

在做完几道 Tarjan 算法的题目后,我意外发现其中判断强连通分量的一题代码写成了:

if(dfn[v] == 0) {
    tarjan(u);
    low[u] = min(low[u], low[v]);
} else {
    low[u] = min(low[u], dfn[v]);
}

而不是:

if(dfn[v] == 0) {
    tarjan(u);
    low[u] = min(low[u], low[v]);
} else if(inStack[v]) {
    low[u] = min(low[u], dfn[v]);
}

依然 AC。请问各位大佬,这个判断是否在栈中的代码是本来就可写可不写还是我做的这题数据太弱?

2022/10/26 21:50
加载中...