双连通分量

[Ir1d]

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

[EndSaH]

有 Tarjan 算法的讲解吗- -

[minghu6]

我写了一篇介绍，作为一个迟到四年的回答😅

[thallium]

@EndSaH
有 Tarjan 算法的讲解吗- -

Tarjan是强连通的算法呀:)

[YJCCity]

可以用 Tarjan 求解呀

[correct1]

@thallium

@EndSaH
有 Tarjan 算法的讲解吗- -

Tarjan是强连通的算法呀:)

tarjan可以求解双连通分量的呀

[Yianlaen]

@thallium

@EndSaH
有 Tarjan 算法的讲解吗- -

Tarjan是强连通的算法呀:)

Tarjan 的 BCC 和 SCC 写在同一份 paper 的吧（

[my-vegetable-has-exploded]

桥的重边是不是去重特判一下就好？

[cbioo]

桥的重边是不是去重特判一下就好？

有的题会定义成重边算两条，也就是都不是桥

[jpy-cpp]

……

[hgzxgzx]

差分优化割边里的较大点与较小点是什么意思

[wxh-233]

能有例题和代码吗

[xiao-ming-hub]

两个点双最多只有一个公共点

这不一定吧，如果有个菊花图 V={1,2,3}, E={(1,2), (1,3), (1,4)}，那点 1 就是割点，也是三个点双 {1,2}, {1,3}, {1,4} 的公共点。

[Larryyu-cs]

两个点双最多只有一个公共点和一个点可以在多个点双中是不同的意思。
你{1,2} 和 {1,3} 两个点双不确实只有一个公共点吗，你要是有两个公共点，这两个点双就会变为更大的一个点双连通分量，与定义相悖

[xiao-ming-hub]

哦明白了，当时我把 “最多” 看成了放在 “两个点双” 前面 / w

[Lskkkno1]

感觉点双最近在 XCPC 中出现的好多，只会边双的选手（比如我）原地去世

[Lucky-Cloud09]

边双 Tarjan 2，应该不用判横叉边 else if (vis[v])，直接 else 就可以了吧

[Lucky-Cloud09]

好像判了也是对的

[BlooshedYellowFlower]

边双的tarjan算法2里的vis数组是没必要的