强连通分量

[Ir1d]

https://oi-wiki.org/graph/scc/

[longlongzhu123]

定义上好像有点问题：

$low[u]$ 定义为以下结点的 $dfn$ 的最小值： $Subtree(u)$ 中的结点；从 $Subtree(u)$ 通过一条不在搜索树上的边能到达的结点。

然而在接下来的描述以及代码中都提到了：这条不在搜索树上的边不能连接到一个非栈点中去。否则，直接按照定义编写代码会得到答案错误。

暂时还未想到很好的解决办法。另外，下文中并没有交代栈的来历。应该在这两处地方阐述清楚，建议修改

[lzy20091001]

将定义改为通过至少一条返祖边能到达的结点？

[thallium]

最近在youtube上看的视频，英语不错的可以看一下，可视化之后就比较好理解了：https://www.youtube.com/watch?v=TyWtx7q2D7Y

[WineChord]

推荐一下 https://www.byvoid.com/zhs/blog/scc-tarjan, 有一个很清晰的图示

[27rabbit-penguin]

Tarjan 中的 j 应该是发音的，不然不会译为塔扬。j应该发/j/的音

[Lourisy]

能不能加个缩点的代码？谢谢

[nalemy]

我总觉得前向边的定义不太准确，既然前向边是从祖先到后代的边，那么树边也是前向边啦？那么那个示意图就不够准确。返祖边（后向边）也存在同样定义上的问题。

[nuo0930]

LCA的tarjan貌似不是Robert Tarjan的

[nalemy]

It is named after Robert Tarjan, who discovered the technique in 1979.

from Tarjan's off-line lowest common ancestors algorithm

[ManlioWu]

请问一下，如果v是被访问过且在栈中，为什么不能用 low[v] 来更新 low[u]

[yuyajun]

同问。别处解释说：//这里用dfn[e[i].v]更新的原因是：这个点可能已经在另一个强连通分量中了但暂时尚未出栈，所以now不一定能到达low[e[i].v]但一定能到达dfn[e[i].v].
但没有找到反例，孩子v能到low[v]，那u应该也能到low[v]，所以理论可以直接更新？

[yuyajun]

https://cs.stackexchange.com/questions/96635/tarjans-scc-example-showing-necessity-of-lowlink-definition-and-calculation-r

[yuyajun]

上面链接说 两种都可以

[27rabbitlt]

如果单纯是求强连通分量，可以证明两种写法是等价的。

[yuyajun]

时隔一段时间好像理解了，正如图例中横叉边，low[8]=low[9]=dfn[7]=7而不是等于low[7]的1

[thallium]

@ET-Shamrock
请问一下，如果v是被访问过且在栈中，为什么不能用 low[v] 来更新 low[u]

因为tarjan论文中low的定义是通过最多一条反向边能到达的最小的dfn，low[v]有可能经过了其他的反向边，所以不能用low[v]来更新。但其实如果用low[v]来更新得到的算法也是对的，因为最多一条反向边这个限制并没有什么用。。。

[AStogov]

这个限制还是有用的，在求割点的时候，考虑如下图：
cut
因为tarjan算法求割点的时候，比较的是当前点的dfn与孩子们的low，如果不止一条反向边，很容易出现莫名其妙的僭越

[ManlioWu]

@thallium

@ET-Shamrock
请问一下，如果v是被访问过且在栈中，为什么不能用 low[v] 来更新 low[u]

因为tarjan论文中low的定义是通过最多一条反向边能到达的最小的dfn，low[v]有可能经过了其他的反向边，所以不能用low[v]来更新。但其实如果用low[v]来更新得到的算法也是对的，因为最多一条反向边这个限制并没有什么用。。。

好的，明白了，谢谢！

[suica]

魔改了一下……能过https://codeforces.com/problemset/problem/427/C
但是不知道对不对

void tarjan(int u) {
  if (dfn[u]) {
    return;
  }
  low[u] = dfn[u] = ++dfcnt;
  stk[++tp] = u;
  instack[u] = 1;
  for (auto to : g[u]) {
    if (!dfn[to] || instack[to]) {
      tarjan(to);
      low[u] = min(low[u], low[to]);
    }
  }
  if (dfn[u] == low[u]) {
    sc++;
    while (stk[tp + 1] != u) {
      scc[sc].push_back(stk[tp]);
      instack[stk[tp]] = 0;
      tp--;
    };
  }
}

[fst20080215]

@yyddm803
我总觉得前向边的定义不太准确，既然前向边是从祖先到后代的边，那么树边也是前向边啦？那么那个示意图就不够准确。返祖边（后向边）也存在同样定义上的问题。

这个本来就是一个认为的概念，哪条边先dfs遍历到那条边就是树边，并没有准确的定义

[Joecai9]

@nuo0930
LCA的tarjan貌似不是Robert Tarjan的

@nuo0930
LCA的tarjan貌似不是Robert Tarjan的

是他的，都是他发明的

[hfhongzy]

Kosaraju 算法的实现，最后循环应为 $n-1$ 到 $0$

[Lourisy]

好的谢谢

…

---原始邮件--- 发件人: "Teng ***@***.***> 发送时间: 2023年11月8日(周三) 下午5:15 收件人: ***@***.***>; 抄送: ***@***.******@***.***>; 主题: Re: [OI-wiki/gitment] 强连通分量 (Discussion #727) 如果单纯是求强连通分量，可以证明两种写法是等价的。 — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.Message ID: ***@***.***>