强连通分量缩点相关
  • 板块学术版
  • 楼主李宇涵
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/2/9 15:45
  • 上次更新2023/10/24 01:19:38
查看原帖
强连通分量缩点相关
211536
李宇涵楼主2023/2/9 15:45

众所周知,求强连通分量(SCC)有两种常见的方法:Tarjan 和 Kosaraju。

目前我感觉 Kosaraju 更好写一些,但是 Kosaraju 的时间常数和空间常数都是 Tarjan 的 22 倍(两次 dfs,建反图)。

所以问问大家,更建议用哪个方法(

2023/2/9 15:45
加载中...