Tarjan 例题

例题

P1656 炸铁路

求割边

 

习题

无向图

poj 1144 network   入门

找割点,读入比较麻烦

uva10765    DCC 易

dark bzoj 1123 BLO  易 DCC

求删除每一个点后算不能连通的点对个数,坑点,(1,2),(2,1)算两个。删除点,实际上是删除点的边,不删除点本身,最后计算答案时要算上“删除”的那个点。

poj 3177  Redundant Paths  DCC  中  

注意重边,缩点后变成树,算叶节点个数x,然后它的一半(向上取整就是答案),因为两个叶节点相连,就形成一个环

bzoj2730  割点  中

割点后遍历连通块,根据割点数量分类讨论

 poj3694 DCC 中

HDU2460  eDCC 难

有向图

POJ - 1236 SCC 入门

LibreOJ - 10095 SCC 易

poj 2762 SCC 中

 cf 1000E SCC 中

poj2942 SCC 难

dark bzoj 2438 SCC 难

 

上一篇:【图论】强连通分量+tarjan算法


下一篇:2021.05.14 tarjan